首页 > 代码库 > poj 1014 Dividing

poj 1014 Dividing

http://poj.org/problem?id=1014

 

思路

大概是裸的多重背包  复杂度

 

#include<iostream>#include<cstdio>#include<algorithm>#include<string.h>using namespace std;const int maxn = 6e4+100;int s[7],dp[maxn];void init(){    memset(dp,0,sizeof(dp));}int main(){    int cas =1;    while (cin>>s[1]>>s[2]>>s[3]>>s[4]>>s[5]>>s[6])    {        init();        int sum =0;        for(int i=1;i<=6;i++)            sum+=i*s[i];        if(sum == 0)            break;        if(sum&1)        {            printf("Collection #%d:\n",cas++);            printf("Can‘t be divided.\n\n");        }        else        {            sum /= 2;            for(int i=1;i<=6;i++)            {                if(s[i]==0) continue;                if(i*s[i] > sum)                {                    for(int j=i;j<=sum;j++)                    {                        dp[j] = max(dp[j],dp[j-i]+i);                    }                }                else                {                    int k=1,t=s[i];                    while (k<t)                    {                        for(int j=sum;j>= k*i;j--)                            dp[j] = max(dp[j],dp[j-i*k]+i*k);                        t-=k,k*=2;                    }                    for(int j=sum;j >=t*i;j--)                    {                        dp[j] = max(dp[j],dp[j-i*t]+i*t);                    }                }            }            if(dp[sum] == sum)            {                printf("Collection #%d:\n",cas++);                printf("Can be divided.\n\n");            }            else            {                printf("Collection #%d:\n",cas++);                printf("Can‘t be divided.\n\n");            }        }    }}

 

poj 1014 Dividing