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