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 |
果断多重背包//若质量总和v为偶数,那么能均分的条件一定是多重背包组合能装满v/2 #include<cstdio> #include<cstring> #include<iostream> using namespace std; int dp[120005] = {0}; int main() { int n[10] = {0},cnt = 1,i,k,j,v; while(1) { v = 0; for(i = 1;i <= 6;i ++) { cin>>n[i]; v += n[i] * i; } if(!v) break; if(v % 2) printf("Collection #%d:\nCan't be divided.\n\n",cnt); else { memset(dp,0,sizeof(dp)); v /= 2; for(i = 1;i <= 6;i ++) { k = 1; while(n[i] > k) { for(j = v;j >= k * i;j --) dp[j] = max(dp[j],dp[j-k*i] + k * i); n[i] -= k; k *= 2; } for(j = v;j >= n[i] * i;j --) dp[j] = max(dp[j],dp[j-n[i]*i] + n[i] * i); } if(dp[v] == v) printf("Collection #%d:\nCan be divided.\n\n",cnt); else printf("Collection #%d:\nCan't be divided.\n\n",cnt); } cnt ++; } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator