hdu 1059 Dividing

链接

[http://acm.hdu.edu.cn/showproblem.php?pid=1059]

题意

就是给你六种物品每种物品的重量是i,有a[i]个问你能不能恰好分为两半

分析

多重背包变形
你只要刚好凑出一半即可
然后加了二进制优化不然超时

代码

#include<iostream>
#include<cstdio>
#include<string.h>
#include<string>
#include<algorithm>
using namespace std;
int a[7],b[200100],dp[200100];
int main(){
    
    //freopen("in.txt","r",stdin);
    int kase=0;
    while(cin>>a[1]>>a[2]>>a[3]>>a[4]>>a[5]>>a[6]){
        int sum=0;
        for(int i=1;i<=6;i++)
        sum+=a[i]*i;
        if(sum==0) break;
        memset(dp,0,sizeof(dp));
        memset(b,0,sizeof(b));
        if(sum&1){
            printf("Collection #%d:\n",++kase);
            printf("Can't be divided.\n\n");
        }
        else{
            sum/=2;
            int cnt=0;
            for(int i=1;i<=6;i++){
                    for(int j=1;j<=a[i];j<<=1)
                   {
                     b[cnt++]=j*i;
                     a[i]-=j;
                   }
                  if(a[i]>0) b[cnt++]=a[i]*i;
            } 
            for(int i=0;i<cnt;i++)
            for(int j=sum;j>=b[i];j--)
            dp[j]=max(dp[j],dp[j-b[i]]+b[i]);
            if(dp[sum]==sum)
            {
                printf("Collection #%d:\n",++kase);
               printf("Can be divided.\n\n");
            }
            else{
                printf("Collection #%d:\n",++kase);
            printf("Can't be divided.\n\n");
            }
        }
    }
    return 0;
}

hdu 1059 Dividing

原文：https://www.cnblogs.com/mch5201314/p/10622429.html