Question

HDU 1059 请具体指出我的程序错误! 一直WA !!

#include<stdio.h>
#include<string.h>

int max(int a,int b){
return a>b?a:b;
}
int main()
{
int ans[10];
int num[10],end,i,sum,j,k,flag;
int J = 0,ou;

while(1)
{
end = sum = flag = ou = 0;
for(i = 1;i <= 6; i ++)
{
scanf("%d",&num[i]);
if(num[i] == 0) ++ end ;

if(num[i]%2 == 0){
ou ++ ;
num[i] = 0;
}else
num[i] = 1;

sum += num[i]*i;
}
if(end == 6) break;

if(ou == 6){
printf("Collection #%d:\n",++J);
printf("Can be divided.\n\n");
continue;
}

sum = sum/2;
memset(ans,0,sizeof(ans));

for(i = 1;i <= 6;i ++)
for(j = 0; j <= num[i] ;j ++)
for(k = sum; k >= i*j ; k --)
{
ans[k] = max(ans[k],ans[k-i*j]+i*j);
if(ans[k] == sum)
flag = 1;
}

printf("Collection #%d:\n",++J);
if(flag)
printf("Can be divided.\n\n");
else
printf("Can't be divided.\n\n");
}
return 0;
}

Answer 1

你这个等于6是什么理论啊？
flag没有初 始化
下面是我的AC代码，用背包做的复杂度是N*M
#include<stdio.h>
const int MAX=20000*6+5;
struct
{
bool visited;
int s[6];
}dp[MAX];
int max[6];
bool check()
{
int i;
for(i=0;i<6;i++)
if(max[i])
return 0;
return 1;
}
int main()
{
int n,i,j,tmp,CS=1,k;
while(scanf("%d",&max[0])!=EOF)
{
n=max[0];
for(i=1;i<6;i++)
{
scanf("%d",&max[i]);
n+=(i+1)*max[i];
}
if(check())
break;
printf("Collection #%d:\n",CS++);
if(n%2)
{
puts("Can't be divided.");
puts("");
continue;
}
n>>=1;
for(i=0;i<=n;i++)
dp[i].visited=0;
dp[0].visited=1;
for(i=0;i<6;i++)
dp[0].s[i]=0;
for(i=0;i<6;i++)
{
for(j=0;j+i+1<=n;j++)
{
if(dp[j].visited==0)
continue;
if(dp[j].s[i]>=max[i])
continue;
if(dp[j+i+1].visited==0)
{
dp[j+i+1].visited=1;
for(k=0;k<6;k++)
dp[j+i+1].s[k]=dp[j].s[k];
dp[j+i+1].s[i]++;
}
}
}
if(dp[n].visited)
puts("Can be divided.");
else
puts("Can't be divided.");
puts("");
}
return 0;
}

追问

1~6对应 6种价值的石头 ! 我只是想知道的错在哪 ! flag 在while 循环里 初始化了!

追答

你直接把石头平均分了当然不对啦
4 0 0 0 1 0 0
Collection #1:
Can't be divided.

这个数据你就不对