algorithm - 无法找到我用于解决 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 都在跟踪解决方案中包含的元素的数量，以便我可以判断分配在玩家数量方面是否相等。如果这些方法是错误的，则提示正确的方向是非常感谢。

Answer 1

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

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

假设 4 名玩家 有经验 2 3 4 5。

你不需要为了总和而旅行:1 到 8，而是做这样的事情:

初始和0

如果你包含第一个元素:0 & 2

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

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

等等

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

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

PS:我解决了这个问题，花了点时间，还挺好玩的。