首页 > 代码库 > poj1014:母函数+优化
poj1014:母函数+优化
题目大意:
有1~6六种宝石,价格分别为1~6 。。给定每种宝石的个数,问能否平分给两个人
分析:
一看显然是个多重背包问题,也可以用母函数做
不过母函数的复杂度是n*v*k,第一次tle了。。
后来发现一种优化方式
当个数大于 6的时候直接把个数设为 5(奇数),6(偶数)。。
discuss 里面有位神牛给出了这个优化的证明:
http://poj.org/showmessage?message_id=342382
我把个数设成60或者61也过了。。
#include <iostream>#include <stdio.h>#include<string.h>#include<algorithm>#include<string>#include<ctype.h>using namespace std;#define MAXN 10000int a[10];bool m[2][150000];int main(){ int cas=1; while(scanf("%d",a+1)) { int t=0; for(int i=2;i<=6;i++) { scanf("%d",a+i); } for(int i=1;i<=6;i++) { if(a[i]>60) { a[i]=a[i]%2?61:60; } t+=a[i]*i; } if(!t) break; printf("Collection #%d:\n",cas++); if(t%2) { puts("Can‘t be divided."); puts(""); continue; } memset(m,0,sizeof(m)); m[0][0]=1; for(int i=1;i<=6;i++) { for(int j=0;j<=t/2;j++) { if(m[(i-1)%2][j]==0) continue; for(int k=0;k<=a[i];k++) { if(k*i+j>t/2) break; m[i%2][k*i+j]=1; } } } if(m[0][t/2]) { puts("Can be divided."); } else { puts("Can‘t be divided."); } puts(""); } return 0;}
poj1014:母函数+优化
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。