Collection #1:Can’t be divided.Collection #2:Can be divided.
这道题很有趣呵呵
你们看我的AC状态：
你再看看题目要求的时间。
我这代码过不过就是看人品吧。
我按照讨论区里面说的，，改进了一下，再看一下AC状态：
我有两份代码，
这份是982MS的：
#include <stdio.h>#include <string.h>#define MAX 401000int dp[MAX] ;int max(int a , int b){return a>b?a:b;}void zeroOnePack(int value , int total){for(int i = total ; i >= value ; –i){dp[i] =max(dp[i] , dp[i-value] + value) ;}}void completePack(int value , int total){for(int i = value ; i <= total ; ++i){dp[i] = max(dp[i] , dp[i-value] + value) ;}}void multiplePack(int value , int count , int total){if(count*value > total){completePack(value , total) ;}else{int k = 1 ;while(k<=count){zeroOnePack(k*value , total);count -= k ;k *= 2 ;}zeroOnePack(count*value , total);}}int main(){int count[10] , c = 1;while(true){int total = 0 ;bool flag = false ;for(int i = 1 ; i <= 6 ; ++i){scanf("%d",&count[i]) ;if(count[i] != 0){flag = true ;}total += count[i]*i ;}if(!flag) break ;printf("Collection #%d:\n",c++) ;if(total%2 == 1) {printf("Can't be divided.\n\n");continue ;}memset(dp,0,sizeof(int)*(total/2+10)) ;for(int i = 1 ; i <= 6 ; ++i){multiplePack(i , count[i] , total/2) ;}if(dp[total/2] == total/2)printf("Can be divided.\n\n") ;elseprintf("Can't be divided.\n\n");}return 0 ;}这份是0MS的：
#include <stdio.h>#include <string.h>#define MAX 401000int dp[MAX] ;int max(int a , int b){return a>b?a:b;}void zeroOnePack(int value , int total){for(int i = total ; i >= value ; –i){dp[i] =max(dp[i] , dp[i-value] + value) ;}}void completePack(int value , int total){for(int i = value ; i <= total ; ++i){dp[i] = max(dp[i] , dp[i-value] + value) ;}}void multiplePack(int value , int count , int total){if(count*value > total){completePack(value , total) ;}else{int k = 1 ;while(k<=count){zeroOnePack(k*value , total);count -= k ;k *= 2 ;}zeroOnePack(count*value , total);}}int main(){int count[10] , c = 1;while(true){int total = 0 ;bool flag = false ;for(int i = 1 ; i <= 6 ; ++i){scanf("%d",&count[i]) ;if(count[i] != 0){flag = true ;}count[i] %= 30 ;total += count[i]*i ;}if(!flag) break ;printf("Collection #%d:\n",c++) ;if(total%2 == 1) {printf("Can't be divided.\n\n");continue ;}memset(dp,0,sizeof(int)*(total/2+10)) ;for(int i = 1 ; i <= 6 ; ++i){multiplePack(i , count[i] , total/2) ;}if(dp[total/2] == total/2)printf("Can be divided.\n\n") ;elseprintf("Can't be divided.\n\n");}return 0 ;}我只做了一点小小的修改，就是把每个value给模30。其实第一份代码可以不通过模30而改进的，，把所有函数写进主函数里可能就减少了耗时。（Ps：我在写博客的时候，又试了一下第一份代码，，变成了600MS，第一份代码应该是肯定能过的代码）。
，人生没有彩排，每一天都是现场直播
