Question

ACM的题 输入一个长度为N的数组，求数组中任意I 项 (1 <I< N) 相加/减所得到的全部数 怎么做啊。

Problem A
Time Limit : 1000/1000ms (Java/Other) Memory Limit : 32768/32768K (Java/Other)
Total Submission(s) : 4 Accepted Submission(s) : 1
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
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
3
1 2 4
3
9 2 1

Sample Output
0
2
4 5

Answer 1

#include <iostream>
using namespace std;

bool dp[101][10001];
int maximum;

int main()
{
int n,temp,c;
while(cin>>n)
{
maximum = 0;
c = 0;
memset(dp,0,sizeof(dp));
dp[0][0] = true;
for(int i=1;i<=n;i++)
{
cin >> temp;
for(int j=0;j<=maximum;j++)
{
if(dp[i-1][j]==false) continue;
dp[i][j] = true;
if(j>temp) dp[i][j-temp] = true;
else dp[i][temp-j] = true;
dp[i][j+temp] = true;
}
maximum+=temp;
}
for(int i=1;i<=maximum;i++)
{
if(dp[n][i]==false) c++;
}
cout << c << endl;
if(c!=0)
{
bool bg = false;
for(int i=1;i<=maximum;i++)
if(dp[n][i]==false)
{
if(bg) cout << " ";
cout << i;
bg = true;
}
cout << endl;
}
}
}