HDU 1709 The Balance

题目：给出一定（n）数量的砝码，每个砝码重a1，a2，a3。。。an，

问题：求出【1~sum】中（sum为各砝码总和）不能被称出的重量；

问题关键：天平两边都可以放砝码，

放在同一端：a[j+k]+=a[j]

　　　　不同端a[abs(j-k)]+=a[j]

         假设原来的砝码都放在右端，则可以把新加的砝码放在左端，得到新重量,此时a[abs(j-k)]+=a[j]。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 110;
int s[maxn],s1[maxn*maxn],s2[maxn*maxn];
void init()
{
    memset(s1,0,sizeof(s1));
    memset(s2,0,sizeof(s2));
}
int main ()
{
    int n;
    while (~scanf("%d",&n))
    {
        init();
        int sum =0;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&s[i]);
            sum+=s[i];
        }
        s1[0] = s1[s[1]] =1;
        for(int i=2;i<=n;i++)
        {
            for(int j=0;j<=sum;j++)
            {
                for(int k=0;k<=s[i];k+=s[i])
                {
                    s2[j+k] += s1[j];
                    s2[abs(j-k)] += s1[j];
                }
            }
            for(int j=0;j<=sum;j++)
            {
                s1[j] = s2[j];
                s2[j] = 0;
            }
        }
        int num =0,cnt=0;
        for(int i=0;i<=sum;i++)
            if(s1[i]==0)
            num++;
        if(num == 0)
           printf("0
");
        else{
            printf("%d
",num);
            for(int i=0;i<=sum;i++)
            {
                if(s1[i]==0)
                {
                    if(cnt)
                        printf(" %d",i);
                    else//cnt =0
                    {
                        printf("%d",i);
                        cnt=1;
                    }
                }
            }
            puts("");
        }
    }
}