首页 > 其他 > 详细

poj 1014 Dividing

时间:2017-08-14 16:13:36      阅读:165      评论:0      收藏:0      [点我收藏+]

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

原文:http://www.cnblogs.com/Draymonder/p/7358010.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!