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 |
刚看完背包9讲之第3讲,照着写了写,贴出来献丑!#include <cstdio> int marbles[7]; int dp[60010]; bool status[60010]; int e[21]; int main() { //freopen("e:/data.txt", "r", stdin); e[1] = 1; for(int i = 2; i <= 20; ++i) { e[i] = e[i - 1] * 2; } int c = 1; while(true) { scanf("%d %d %d %d %d %d", &marbles[1], &marbles[2], &marbles[3], &marbles[4], &marbles[5], &marbles[6]); if(marbles[1] == 0 && marbles[2] == 0 && marbles[3] == 0 && marbles[4] == 0 && marbles[5] == 0 && marbles[6] == 0) { break; } printf("Collection #%d:\n", c++); int s = 0; for(int i = 1; i <= 6; ++i) { s += marbles[i] * i; } if(s & 1) { printf("Can't be divided.\n\n"); continue; } int pack = s / 2; for(int i = 0; i <= pack; ++i) { dp[i] = 0; status[i] = false; } status[0] = true; int cur_value; for(int i = 1; i <= 6; ++i) { if(marbles[i] * i >= pack) { cur_value = i; for(int j = cur_value; j <= pack; ++j) { if(status[j - cur_value] == true) { dp[j] = dp[j] > dp[j - cur_value] + cur_value ? dp[j] : dp[j - cur_value] + cur_value; status[j] = true; } } } else { if(marbles[i] > 1) { bool flag = true; int k = 1; int rest = marbles[i]; while(flag) { if(e[k] > rest) { cur_value = rest * i; flag = false; } else if(e[k] == rest){ cur_value = rest * i; flag = false; } else { cur_value = e[k] * i; rest -= e[k++]; } for(int j = pack; j >= cur_value; --j) { if(status[j - cur_value] == true) { dp[j] = dp[j] > dp[j - cur_value] + cur_value ? dp[j] : dp[j - cur_value] + cur_value; status[j] = true; } } } } else if(marbles[i] == 1) { cur_value = i; for(int j = pack; j >= cur_value; --j) { if(status[j - cur_value] == true) { dp[j] = dp[j] > dp[j - cur_value] + cur_value ? dp[j] : dp[j - cur_value] + cur_value; status[j] = true; } } } } } if(status[pack] == true && dp[pack] == pack) { printf("Can be divided.\n\n"); } else { printf("Can't be divided.\n\n"); } } return 0; } Followed by:
Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator