社区讨论

求助大佬,n*m为什么会TLE

P10911 [蓝桥杯 2024 国 B] 数位翻转参与者 3已保存回复 7

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
7 条
当前快照
1 份
快照标识符
@mhjrxdgu
此快照首次捕获于
2025/11/04 07:31
4 个月前
此快照最后确认于
2025/11/04 07:31
4 个月前
查看原帖
代码如下:
CPP
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;


const int INF = 1e18;


class solution
{
    public:
        void solve();
};


void solution::solve()
{
    int n,m;cin>>n>>m;
    vector<int>a(n+2);
    for(int i=1;i<=n;i++)
        cin>>a[i];

    vector<int>b(n+2);

    for(int i=1;i<=n;i++)
    {
        int res = 0;
        int bt = 32-__builtin_clz(a[i]);
        for(int j=0;j<bt;j++)
            if(a[i]>>j&1)
                res += 1<<(bt-j-1);
        b[i] = res;
    }
    b[0] = 0;
    a[0] = 0;
    a[n+1] = b[n+1] = 0;
    // for(int i=1;i<=n;i++)
    //     cout<<b[i]-a[i]<<' ';
    // cout<<endl;
    LL f[n+2][m+1][2];
    for(int i=0;i<=n+1;i++)
        for(int j=0;j<=m;j++)
            f[i][j][0] = f[i][j][1] = -INF;
    f[0][0][0] = 0;

    for(int i=1;i<=n+1;i++)
    {
        for(int j=0;j<=m;j++)
        {
            // f[i][j][1] = max(f[i-1][j-1][0]+b[i],f[i-1][j][1] + b[i]);
            f[i][j][0] = max(f[i][j][0],f[i-1][j][0] + a[i]);
            f[i][j][0] = max(f[i][j][0],f[i-1][j][1] + a[i]);
            if(j)
                f[i][j][1] = max(f[i][j][1],f[i-1][j-1][0] + b[i]);
            f[i][j][1] = max(f[i][j][1],f[i-1][j][1] + b[i]);
            // f[i][j][0] = max(f[i-1][j][0],f[i-1][j][1]) + a[i];
        }
    }
    LL ans = 0;

    for(int i=0;i<=m;i++)
        // cout<<f[n][i][0]<<' '<<f[n][i][1]<<endl;
        ans = max(ans,max(f[n+1][i][0],f[n+1][i][1]));
    cout<<ans<<endl;

}


signed main()
{
    ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    int T = 1;
    solution AC;
    //cin>>T;
    while(T --)
    {
        AC.solve();
    }
    return 0;
}
什么错误都可以接受,除了TLE实在是找不到代码原因,仔细看了事件限制,也确实是1s,按理说我这不可能过1e8的计算次数呀.T了三个点,13,15,18,求助大佬了,因为确实找不到T的原因qaq,谢谢佬们

回复

7 条回复,欢迎继续交流。

正在加载回复...