http://acm.hdu.edu.cn/showproblem.php?pid=1059
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #define maxn 2000000 5 using namespace std; 6 7 int dp[maxn]; 8 int a[maxn]; 9 int w[maxn]; 10 int sum,v; 11 12 int main() 13 { 14 int cas=0; 15 while(scanf("%d",&a[1])!=EOF) 16 { 17 sum=a[1]; 18 for(int i=2; i<=6; i++) 19 { 20 scanf("%d",&a[i]); 21 sum+=a[i]*i; 22 } 23 if(!sum) break; 24 printf("Collection #%d: ",++cas); 25 if(sum&1) 26 { 27 printf("Can't be divided. "); 28 continue; 29 } 30 memset(dp,0,sizeof(dp)); 31 int cnt=1; 32 for(int i=1; i<=6; i++) 33 { 34 for(int j=1; j<=a[i]; j<<=1) 35 { 36 w[cnt++]=j*i; 37 a[i]-=j; 38 } 39 if(a[i]>0) 40 { 41 w[cnt++]=a[i]*i; 42 } 43 } 44 v=sum/2; 45 for(int i=1; i<cnt; i++) 46 { 47 for(int j=v; j>=w[i]; j--) 48 { 49 dp[j]=max(dp[j-w[i]]+w[i],dp[j]); 50 } 51 } 52 if(dp[v]==sum/2) 53 { 54 printf("Can be divided. "); 55 } 56 else printf("Can't be divided. "); 57 } 58 return 0; 59 }