首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。