HDOJ 1709 The Balance(母函数)

The Balance

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

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

Source

HDU 2007-Spring Programming Contest

Recommend

lcy

 //对每个砝码可以不用，也可以放到左边或右边。。。。。

 #include <iostream>
 #include <cstdio>
 #include <cstring>

 using namespace std;

 int n,m;
 int a[];
 int c1[],c2[];
 const int cc=;

 int main()
 {
 while(scanf("%d",&n)!=EOF)
 {
     int m=;
     for(int i=;i<=n;i++)
     {
         scanf("%d",&a[i]);
         m+=a[i];
     }

     memset(c1,,sizeof(c1));
     memset(c2,,sizeof(c2));

     for(int i=-a[];i<=a[];i+=a[])
     {
         c1[i+cc]=;
     }

     for(int i=;i<=n;i++)
     {
         for(int j=-m;j<=m;j++)
         {
             for(int k=-a[i];k+j<=m&&k<=a[i];k+=a[i])
             {
                 c2[k+j+cc]+=c1[j+cc];
             }
         }
         for(int j=-m;j<=m;j++)
         {
             c1[j+cc]=c2[j+cc];
             c2[j+cc]=;
         }
     }

     int aas[]={};
     int ans=;
     for(int i=;i<=m;i++)
     {
         if(c1[i+cc]||c1[-i+cc]) ;
         else
         {
             aas[ans]=i;
             ans++;
         }
     }

     printf("%d\n",ans);
     for(int i=;i<ans;i++)
     {
         if(i==)
             printf("%d",aas[i]);
         else
             printf(" %d",aas[i]);
     }
     if(ans)
     putchar();

 }

     return ;
 }