The Balance

Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 7089 Accepted Submission(s): 2923

Problem Description

Now you are asked to measure a dose of medicine with a balance and a number of weights. Certainly it is not always achievable. So you should find out the qualities which cannot be measured from the range [1,S]. S is the total quality of all the weights.

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

Sample Output

题目的意思呢，说实话看了很久才看懂，英语差就是心塞。意思是现在有n个砝码，每个质量为a[i]，问1~砝码质量之和不能称出来的重量有几个，有的话输出来。

还是母函数，不过注意因为是天平称东西，所以不仅仅是加，减也是可以得哦~4kg和5kg的砝码也能称出来1kg的物品~~~

看代码：

#include<iostream>
#include<cstring>
#include<algorithm>
#include<math.h>
#include<cstdio>
using namespace std;
const int maxn= 10005;
int a[maxn],b[maxn],ans[maxn];
int n,v,t,num;
int main(){
	while(cin>>n){
		memset(a,0,sizeof(a));
		memset(b,0,sizeof(b));
		cin>>v;
		a[0]=1;
		a[v]=1;
		t=v;
		for(int i=1;i<n;i++){
			cin>>v;
			t+=v;
			for(int j=0;j<=t;j++){
				b[j]+=a[j];
				b[v+j]+=a[j];
				if(j-v>=0)                        //注意这里！
					b[j-v]+=a[j];
				else
					b[v-j]+=a[j];
			}
			for(int j=0;j<=t;j++){
				a[j]=b[j];
				b[j]=0;
			}
		}
		num=0;
		for(int i=0;i<t;i++)                            //输出别输错了按要求来
			if(a[i]==0){
				ans[num]=i;
				num++;
			}
		cout<<num<<endl;
		if(num!=0){
			for(int i=0;i<num-1;i++)
				cout<<ans[i]<<" ";
			cout<<ans[num-1]<<endl;
		}
	}
	return 0;
}

天天向上~~~~加油！