hdu 1709 The Balance

http://acm.hdu.edu.cn/showproblem.php?pid=1709
View Code
 1 /*
 2 砝码称重
 3 */
 4 
 5  
 6 #include<stdio.h>
 7 #include<string.h>
 8 int f(int x,int y)
 9 {
10     if(x>y) return x-y;
11     else return y-x;
12 }
13 int main()
14 {
15     
16 
17     int n;
18     int p[10010];
19     int sum[10010];
20     int temp[10010];
21     int a[105];
22     int i,j,k,l;
23     int totall;
24     while(~scanf("%d",&n))
25     {
26         int count=0;
27         l=0;
28             memset(sum,0,sizeof(sum));
29             memset(temp,0,sizeof(temp));
30         totall=0;
31         for(i=1;i<=n;i++)
32         {
33             scanf("%d",&a[i]);
34             totall+=a[i];
35         }
36         sum[a[1]]=1;
37         sum[0]=1;//注意不要漏这个初始化 
38         for(i=2;i<=n;i++)
39         {
40             for(j=0;j<=totall;j++)
41             {
42                   for(k=0;k<=a[i];k+=a[i])
43                 {
44                     temp[j+k]+=sum[j]; 
45                     temp[f(j,k)]+=sum[j];//砝码不一定放在一边 
46                 }
47             }
48             for(j=0;j<=totall;j++)
49             {
50                 
51                     sum[j]=temp[j];
52             temp[j]=0;
53                 
54             }
55         }
56         
57         
58         for(i=1;i<=totall;i++)
59         {
60             if(sum[i]==0)
61             {
62                 count++;
63                 p[l++]=i;
64             }
65         }
66         if(count) 
67         {
68             printf("%d\n",count);
69             printf("%d",p[0]);
70             for(i=1;i<l;i++)
71             printf(" %d",p[i]);
72             printf("\n");
73         }
74         else printf("0\n");
75         
76     }
77 }