首页 > 代码库 > hdu1709（母函数）
hdu1709（母函数）
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1709
题意: 给你一个n，表示n个物品，下面有n个数，表示n个物品的重量，然后进行称量，每个物品只有一件，看不能称出的价值有几个。
分析：母函数裸题，再处理一下相减的情况。
#include <cstdio>#include <cstring>#include <cmath>#include <iostream>#include <algorithm>#include <queue>#include <cstdlib>#include <vector>#include <set>#include <map>#define LL long long#define mod 1000000007#define inf 0x3f3f3f3f#define N 10010using namespace std;int c1[N],c2[N],a[N],b[N];int main(){ int n,sum; while(scanf("%d",&n)>0) { sum=0; for(int i=1;i<=n;i++) scanf("%d",&a[i]),sum+=a[i]; memset(c1,0,sizeof(c1)); memset(c2,0,sizeof(c2)); memset(b,0,sizeof(b)); for(int i=0;i<=1;i++)c1[a[1]*i]=1; for(int i=2;i<=n;i++) { for(int j=0;j<=sum;j++) { for(int k=0;k<=1&&k*a[i]+j<=sum;k++) c2[j+k*a[i]]+=c1[j]; } memcpy(c1,c2,sizeof(c1)); memset(c2,0,sizeof(c2)); } for(int i=sum;i>0;i--) { if(c1[i]) for(int j=1;j<i;j++) { if(c1[j])b[i-j]=1; } } int num=0; for(int i=1;i<=sum;i++) { if(!c1[i]&&!b[i])c2[num++]=i; } printf("%d\n",num); if(num) { for(int i=0;i<num-1;i++)printf("%d ",c2[i]); printf("%d\n",c2[num-1]); } }}
hdu1709（母函数）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。