hdu1709（母函数）

时间：2021-03-30 20:54:39

题目链接：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 10010

using namespace std;

int c1[N],c2[N],a[N],b[N];

int main()

{

    int n,sum;

    while(scanf("%d",&n)>)

    {

        sum=;

        for(int i=;i<=n;i++)

            scanf("%d",&a[i]),sum+=a[i];

        memset(c1,,sizeof(c1));

        memset(c2,,sizeof(c2));

        memset(b,,sizeof(b));

        for(int i=;i<=;i++)c1[a[]*i]=;

        for(int i=;i<=n;i++)

        {

            for(int j=;j<=sum;j++)

            {

                for(int k=;k<=&&k*a[i]+j<=sum;k++)

                    c2[j+k*a[i]]+=c1[j];

            }

            memcpy(c1,c2,sizeof(c1));

            memset(c2,,sizeof(c2));

        }

        for(int i=sum;i>;i--)

        {

            if(c1[i])

            for(int j=;j<i;j++)

            {

                if(c1[j])b[i-j]=;

            }

        }

        int num=;

        for(int i=;i<=sum;i++)

        {

            if(!c1[i]&&!b[i])c2[num++]=i;

        }

        printf("%d\n",num);

        if(num)

        {

            for(int i=;i<num-;i++)printf("%d ",c2[i]);

            printf("%d\n",c2[num-]);

        }

    }

}

相关文章