首页 > 代码库 > [多重背包+二进制优化]HDU1059 Dividing
[多重背包+二进制优化]HDU1059 Dividing
题目链接
题目大意：
两个人要把一堆宝珠，在不能切割的情况下按照价值平分，他们把宝珠分成6种价值，每种价值的宝珠n个。 n<=200000
思考：
首先如果加和下来的价值是一个偶数 那么还分毛啊，直接gg.
之后多重背包二进制优化 转换为 01背包。
我们可以把价值 同时当做宝珠的空间和价值。
那么我们现在要求的是 在 空间为一半的情况下，能否找到价值为 一半的情况。
1 #include <cstdio> 2 #include <algorithm> 3 #include <cstring> 4 int dp[200005],n[7],V[105],W[100]; 5 6 int main(){ 7 int k=0; 8 while(scanf("%d%d%d%d%d%d",&n[1],&n[2],&n[3],&n[4],&n[5],&n[6])!=EOF && (n[1]||n[2]||n[3]||n[4]||n[5]||n[6])){ 9 printf("Collection #%d:\n",++k);10 int i,j,sum=0,mid;11 for(i=1;i<=6;i++) sum+=i*n[i];12 if(sum%2){13 printf("Can‘t be divided.\n\n");14 continue;15 }16 else mid = sum/2;17 memset(dp,0,sizeof(dp)); //切记不要忘了初始化 18 int count=0,temp,flag=1;19 //这块是二进制优化 20 for(i=1;i<=6;i++){21 temp=1;22 while(n[i]>=temp){23 V[++count]=i*temp;24 W[count]=i*temp;25 n[i]-=temp;26 temp*=2;27 }28 if(n[i]>0){29 V[++count]=i*n[i];30 W[count]=i*n[i];31 }32 }33 //上面是二进制优化 34 for(int i=1;i<=count && flag;i++)35 for(int j=mid;j>=V[i] && flag;j--){36 dp[j] = std::max(dp[j],dp[j-V[i]]+W[i]);37 if(dp[j]==mid){ 38 printf("Can be divided.\n\n");39 flag=0;40 }41 }42 if(flag){43 printf("Can‘t be divided.\n\n");44 }45 }46 return 0;47 }
[多重背包+二进制优化]HDU1059 Dividing
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。