无法找到我用于解决 spoj CWC15 的代码有什么问题

Question

我无法找到 spoj 的记忆和制表出了什么问题 http://www.spoj.com/problems/CWC2015/.If 你可以指出为什么这两个代码给出了各自的错误，这将非常有用。

1--记忆错误--超过时间限制。不知道为什么生成随机案例并在 ideone 上测试大多数解决方案不到一秒钟就出来了。

#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
#include<cstring>
using namespace std;
#define max 20000000

int a[40];
int n;
int m;
long long sum1;
bool dp[40][max];

int solve(long long sum,int x,int k)
{
    if(sum==0)
    {
        if(k==m)
        {
            return true;
        }
        else
        {
            return false;
        }
    }
    else if(x==n)
    {
        return false;
    }
    else if(dp[x][sum])
    {
        return dp[x][sum];
    }
    else
    {
        return dp[x][sum]=(solve(sum,x+1,k)||solve(sum-a[x],x+1,k+1));
    }
}


int main()
{
    int t;
    scanf("%d",&t);
    for(int l=1;l<=t;l++)
    {
        scanf("%d",&n);
        m=n/2;
        long long sum=0;
        memset(dp,0,sizeof(dp));
        for(int i=0;i<n;i++)
        {
            scanf("%d",&a[i]);
            sum+=a[i];
        }
        printf("Case %d: ",l);
        if(n%2)
        {
            printf("No\n");
            continue;
        }
        if(sum%2)
        {
            printf("No\n");
            continue;
        }
        sum=sum/2;
        if(solve(sum,0,0))
        {
            printf("Yes\n");
        }
        else
        {
            printf("No\n");
        }
    }
    return 0;
}

2-列表 Error-Sigsegv(Segmentation fault) 我知道分段错误可能是由于采用太大的数组引起的。但代码在 ideone 上完美运行。

#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
#include<cstring>
using namespace std;
#define max 20000000

int a[40];
int n;
long long sum;
bool dp[max+1][41];


bool solve()
{
    int k=0;
    //cout<<"sum is  "<<sum<<endl;
    for (int i = 0; i <= n; i++)
      dp[0][i] = true;
    for (long long i = 1; i <= sum; i++)
      dp[i][0] = false;

     for (long long i = 1; i <= sum; i++)
     {
       for (int j = 1; j <= n; j++)
       {
         dp[i][j] = dp[i][j-1];
         if (i >= a[j-1])
           dp[i][j] = dp[i][j] || dp[i - a[j-1]][j-1];
         if(i==sum && dp[i-a[j-1]][j-1])
         {
           k+=1;
         }
       }
     }

     /*cout<<k<<endl;*/

     return (dp[sum][n] && k==n/2);
}

int main()
{
    int t;
    scanf("%d",&t);
    for(int l=1;l<=t;l++)
    {
        scanf("%d",&n);
        sum=0;
        memset(dp,0,sizeof(dp));
        for(int i=0;i<n;i++)
        {
            scanf("%d",&a[i]);
            sum+=a[i];
        }
        printf("Case %d: ",l);
        if(n%2)
        {
            printf("No\n");
            continue;
        }
        if(sum%2)
        {
            printf("No\n");
            continue;
        }
        sum=sum/2;
        if(solve())
        {
            printf("Yes\n");
        }
        else
        {
            printf("No\n");
        }
    }
    return 0;
}

注意-在这两个程序中，k 都在跟踪解决方案中包含的元素数量，以便我可以判断根据玩家数量分配是否相等，或者 not.If 这些方法是错误的提示正确的方向将不胜感激。

Answer 1

建议：由于复杂性，您解决问题的方式将行不通。虽然 space 复杂度可以工作（限制为 1536MB 并且使用的 space 约为 785MB），但是时间复杂度对于 5s 的时间限制来说太高了。估计 10^8 可以在 1 秒内安全执行。如果只提交代码的初始化部分，将超过时间限制（我已经这样做了以验证）。

解决方法：您不需要遍历 1 to 200 00 000 的所有总和，而只是在包含 ith 播放器时迭代生成的总和。

假设 4 players 有经验 2 3 4 5。

你不需要为了钱而旅行：1 to 8，而是做这样的事情：

初始总和0

如果包含第一个元素：0 和 2

如果包含第二个元素：0、2、3、4

如果包含第 3 个元素：0、2、3、4、6、7

等等

现在这样最多可以达到2^N。因此，维护一个 20000000 的 int 映射，如果已经存在，则不要将数字放入队列中。这将解决迭代 20000000 * 40 的问题，以迭代唯一的可达总和值（复杂性将取决于输入的性质）。

现在，如果您达到了想要的金额，那么它就可以到达了。观察两支球队中相同数量的球员：我有一个提示给你，记住我提到 "map of int of 20000000"，我说 int 因为这张地图也可以用来存储有多少数字可以达到特定的总和。使用按位运算符对此信息进行编码。您只需要维护计数而不是包含哪个特定元素。

PS: 我解决了这个问题，花了一些时间，很有趣。

无法找到我用于解决 spoj CWC15 的代码有什么问题

Unable to find what's wrong with my code for solve spoj CWC15

algorithm

dynamic-programming

memoization

subset-sum