c++ - 这些代码与性能有关吗？一个非常快，另一个超过时间限制

Question

我在 Codechef 上遇到了一个问题!好吧，我能够为其制定一个动态编程解决方案，但它只通过了三分之一的测试用例!

当我遇到 author 的解决方案时，它与我的非常接近!但即使在尝试(对我的代码进行所有可能的逻辑更改)之后，我的解决方案仍无法正常工作并且未通过测试用例!

我的代码(我必须把它作为一个整体发布，因为我不能简单地理解为什么它这么慢!)

#include<bits/stdc++.h>
using namespace std;
int A[5001];
long long DP[5001][5001];
int T,i,j;
int N,K,l;
int main()
{
    scanf("%d",&T);
    for(;T--;)
    {
        scanf("%d%d",&N,&K);
        for(i=1;i<=N;i++)
                scanf("%d",&A[i]);
 //       for(i=1;i<=K;i++)
 //           DP[0][i]=INT_MIN;

       for(i=0;i<=N;i++)
            for(j=1;j<=K;j++)
                DP[i][j]=INT_MIN;

        for(i=1;i<=N;i++)
            {
                int temp=0,low;
                for(l=i;l>=1;l--)
                {
                    if(temp|A[l] >temp)
                    {
                        low=min(l,K);
                        temp|=A[l];
                        for(j=1;j<=low;j++)
                            DP[i][j]=max(DP[l-1][j-1]+temp,DP[i][j]);

                    }
                }
            }
        printf("%lld\n",DP[N][K]);
    }
    return 0;
}  

我尝试了什么？

将 cin cout 与 ios::sync_with_stdio(0); 一起使用，而不是 scanf printf。使用 memset 清除 DP 数组!声明变量，全局而不是本地(它们是我的代码和作者代码之间的差异)。然后我尝试提交作者的代码只是为了检查它是否真的有效。确实如此!

最初我有一个 Memoized 版本，我将其更改为 DP，但仍然无法使用。

我使用 for 循环只是因为在性能方面它们被认为比 while 循环更好!

注意:我也可以将 INT_MIN 的设置更改为 0，我也试过了。不起作用!

作者的解决方案

#include <bits/stdc++.h>
#define rf freopen("in.in", "r", stdin)
#define wf freopen("out.out", "w", stdout)
#define rep(i, s, n) for(int i=int(s); i<=int(n); ++i)
using namespace std;
const int mx = 1e5+10;

int n, t, k;
int a[mx];
long long calc[5111][5111];

int main()
{
    //rf;// wf;

    scanf("%d", &t);
    while(t--)
    {
        memset(calc, 0, sizeof calc);

        scanf("%d %d", &n, &k);
        rep(i, 1, n)
            scanf("%d", &a[i]);

        rep(i, 1, n)
        {
            int cur = 0, next = 0;
            for(int j = i; j; --j)
            {
                next = cur | a[j];
                if(cur == next)
                    continue;

                rep(l, 1, min(k-1, j-1))
                    calc[i][l+1] = max(calc[j-1][l]+next, calc[i][l+1]);

                cur = next;
            }
            calc[i][1] = cur;
        }
        printf("%lld\n", calc[n][k]);
    }

    return 0;
} 

由于声誉原因我无法发布图片，但我的解决方案超过了第二和第三个子任务的每个测试用例。

以防万一，如果你需要问题陈述Problem(codechef)但我认为比较这些代码不需要它!

Answer 1

注意运算符优先级:

temp|A[l] >temp

将被评估为

temp|(A[l] >temp)