The Balance |
| Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) |
| Total Submission(s): 135 Accepted Submission(s): 88 |
| 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 31 2 439 2 1 |
| Sample Output 024 5 |
| Source HDU 2007-Spring Programming Contest |
| Recommend lcy |
/*题意：给出n个砝码的质量，让你求出在[1,s]范围内不能组成的质量，s是质量总和，这个题不一样的地方是天平两边都可以放砝码初步思路：可以看成一个背包问题，每个取或不取，但是这个题有一个新的状态，就是*/#includeusing namespace std;int v[10010];int dp[10010];//dp[i]表示i金额能组成或不能组成int vis[10010];//记录一下能组成的金额int n;int s=0;void init(){ memset(vis,0,sizeof vis); memset(dp,0,sizeof dp); s=0;}int main(){ // freopen("in.txt","r",stdin); while(scanf("%d",&n)!=EOF){ init(); for(int i=1;i<=n;i++){ scanf("%d",&v[i]); s+=v[i]; } vis[0]=1; for(int i=1;i<=n;i++){ memset(dp,0,sizeof dp); for(int j=0;j<=s;j++){ if(vis[j]){ //j金额能组成 dp[j+v[i]]=1;//加上当前金额那么也是可以的 dp[abs(j-v[i])]=1;//减去这个金额的也是可以的 } } for(int j=0;j<=s;j++){ if(dp[j]) vis[j]=1; } } int res=0; for(int i=1;i<=s;i++) if(!vis[i]) res++; printf("%d\n",res); if(res==0) continue; int f=0; for(int i=1;i<=s;i++){ if(!vis[i]){ if(f==0){ printf("%d",i); f=1; }else{ printf(" %d",i); } } } printf("\n"); } return 0; }