题意:已知有N个不同的砝码,求这N个不同砝码不能称量的重量
分析:与一般的母函数类似,只是还要多考虑一步,就是砝码并不定都放一边
for(int i=1;i<=n;i++)
{ for(int j=0;j<=maxn;j++){ if(j+p[i]<=maxn)num1[j+p[i]]+=num[j];num1[abs(j-p[i])]+=num[j];//核心部分都加了这么一句}for(int j=0;j<=maxn;j++)num[j]=num1[j];}#include#include #include using namespace std;int num1[10010],num[10010],n;int p[110],ans[11000],maxn;void solve(){ memset(num1,0,sizeof(num1)); memset(num,0,sizeof(num)); num1[0]=num[0]=1; for(int i=1;i<=n;i++) { for(int j=0;j<=maxn;j++) { if(j+p[i]<=maxn) num1[j+p[i]]+=num[j]; num1[abs(j-p[i])]+=num[j]; } for(int j=0;j<=maxn;j++) num[j]=num1[j]; }}int main(){ while(scanf("%d",&n)==1) { maxn=0; for(int i=1;i<=n;i++) { scanf("%d",&p[i]); maxn+=p[i]; } solve(); int c=0; for(int i=1;i<=maxn;i++) { if(num[i]==0) ans[c++]=i; } printf("%d\n",c); if(c!=0) { printf("%d",ans[0]); for(int i=1;i