Input The input consists of multiple test cases, and each case begins with a single positive integer N (1<=N<=100) on a line by itself indicating the number of weights you have. Followed by N integers Ai (1<=i<=N), indicating the quality of each weight where 1<=Ai<=100.
Output For each input set, you should first print a line specifying the number of qualities which cannot be measured. Then print another line which consists all the irrealizable qualities if the number is not zero.
Sample Input 3 1 2 4 3 9 2 1
Sample Output 0 2 4 5 做完这题，有必要重新理解下生成函数的功能及其作用：我们说（1+x+x^2）*（1+x^2+x^4+x^6）*（1+x^3+x^6+x^9+x^12）的运算结果的x^j的系数表示组合成j的组合数，那么想想（1+x+x^2）*（1-x^2-x^4-x^6）这样？如果里面有负号，则代表的有事什么呢?拿这道题来说，每种砝码既可以放在右盘，又可以放在左盘，（若按左物右码来说），放在左盘那就取减号，放在右盘就取加号。当然最终我们将指数看为正数，所有求的的系数要取绝对值！ 在生成函数题目里，这是一道相当不错的题目！ #include<cstdio> #include<cmath> #include<algorithm> using namespace std; #define N 10000+10 int num,arr[N],curnum[N],sumnum[N],buf[N]; int main() { freopen("zx.in","r",stdin); freopen("zx.out","w",stdout); while(scanf("%d",&num)!=EOF) { int sum=0; for(int i=1;i<=num;i++) { scanf("%d",&arr[i]); sum+=arr[i]; } memset(curnum,0,sizeof(curnum)); memset(sumnum,0,sizeof(sumnum)); for(int i=0;i<=arr[1];i+=arr[1]) sumnum[i]=1; for(int i=2;i<=num;i++) { for(int j=0;j<=sum;j++) { for(int k=0;k+j<=sum&&k<=arr[i];k+=arr[i]) { if(k>=j) curnum[k-j]+=sumnum[j];//减的情况（左大于右） else curnum[j-k]+=sumnum[j];//减的情况（右大于左） //curnum[abs(j-k)]+=sumnum[j] ——>减的情况总体写法 curnum[j+k]+=sumnum[j];//加的情况 } } for(int j=0;j<=sum;j++) { sumnum[j]=curnum[j]; curnum[j]=0; } } int ans=0,t=0; for(int i=1;i<=sum;i++) if(sumnum[i]==0) { ans++; t++; buf[t]=i; } //注意这里输出格式的设计。 printf("%d",ans); for(int i=1;i<=t;i++) printf(i==1?"/n%d":" %d",buf[i]); printf("/n"); } return 0; }
