Я не могу найти, что происходит не так как в мемотизации, так и в табулировании для 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-tabulation Error-Sigsegv (ошибка сегментации) Я знаю, что ошибка сегментации может быть вызвана слишком большим размером массива. Но код отлично работает на 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 отслеживает количество включенных элементов в решение, чтобы я мог сказать, является ли распределение равным с точки зрения количества игроков или нет. Если эти подходы неверны, был бы очень признателен намек на правильное направление.