首页 > 代码库 > 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]);        }    }}
View Code

 

hdu1709(母函数)