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 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-]);
}
}
}
上一篇:Access denied for user 'root'@'localhost' (using password: YES)的解决


下一篇:尚硅谷面试第一季-11MyBatis中当实体类中的属性名和表中的字段名不一样怎么办