| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
help!help,和别人ac的源码对过答案都对,不知为何wa,我用的是dp,用f[i]记录,标记是否可以组成i,是否有特殊测试数据,望各位高手指教//#define debug 1
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#define INF 30000
#define NMAX 500000
int a[7];
bool f[NMAX];
int sum;
int solve()
{
int i,k,p,t,last,flag;
// bool *f=new bool[sum/2+3];
memset(f,0,sizeof(f));
f[0]=1;
for(i=1;i<=a[1];i++)
f[i]=1;
for(i=2;i<=6;i++)
{
if(a[i]==0)
continue;
for(k=0;k<i;k++)
{
t=k;
/* flag=0;
while(!f[t])
{
t+=i;
if(t>sum/2)
{
flag=1;
break;
}
}
if(flag)
continue;
last=a[i];*/
while(t<=sum/2)
{
if(f[t])
last=a[i];
else
{
if(last)
{
f[t]=1;
last--;
}
}
t+=i;
}
if(f[sum/2]==1)
{
// delete f;
return 1;
}
}
}
if(f[sum/2]==1)
{
return 1;
}
// delete f;
return 0;
}
int main()
{
#if _DEBUG
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
int i;
int flag=0;
int t=1;
while(1)
{
flag=0;
sum=0;
for(i=1;i<=6;i++)
{
scanf("%d",&a[i]);
sum+=a[i]*i;
if(a[i])
flag=1;
}
if(flag==0)
break;
if(t>1)
printf("\n");
printf("Collection #%d:\n",t++);
if(sum%2)
printf("Can't be divided.\n");
else if(solve()==0)
printf("Can't be divided.\n");
else
printf("Can be divided.\n");
}
#if _DEBUG
fclose(stdin);
fclose(stdout);
#endif
return 1;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator