HDU 1709 The Balance(親関数**)

The Balance
Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 4293    Accepted Submission(s): 1725
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
 
 
 
各分銅は右盤にも左盤にも置けますが、(左物右符号で言えば)、左盤に置くとマイナス記号を取り、右盤に置くとプラス記号を取ります.
 
标题:1つの天秤、いくつかの分銅、あなたに各分銅の重量をあげて、あなたにこの天秤と分銅でどんな重量を量ることができませんか?分銅は天秤の左右に置いてもいいですよ.  題解:母関数、分銅モデル、セットテンプレート、具体的にはアルゴリズムがまとめた母関数を参照してください.と言いたかったのですが、今回は変種で、そのままテンプレートをはめて泣いてしまいました.分銅は両側に置くことができるので、1つのコードtemp[abs(j-k)]+=a[j]を追加します.例えば9と4は重さが5のものを量ることができて、努力して理解するようにしましょう~
 

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>



using namespace std;



const int N=10010;



int n,num[N],res[N];

int c1[N],c2[N];



int main(){



    //freopen("input.txt","r",stdin);



    while(~scanf("%d",&n)){

        int sum=0;

        for(int i=1;i<=n;i++){

            scanf("%d",&num[i]);

            sum+=num[i];

        }

        memset(c1,0,sizeof(c1));

        memset(c2,0,sizeof(c2));

        for(int i=0;i<=num[1];i+=num[1])

            c1[i]=1;

        for(int i=2;i<=n;i++){

            for(int j=0;j<=sum;j++)

                for(int k=0;k+j<=sum && k<=num[i];k+=num[i]){

                    if(k>=j)    

                        c2[k-j]+=c1[j]; //    （    ）

                    else

                        c2[j-k]+=c1[j]; //    （    ）

                                        //c2[abs(j-k)]+=c1[j] ——>          

                    c2[j+k]+=c1[j];

                }

            for(int j=0;j<=sum;j++){

                c1[j]=c2[j];

                c2[j]=0;

            }

        }

        int ans=0;

        for(int i=1;i<=sum;i++)

            if(c1[i]==0)

                res[ans++]=i;

        printf("%d",ans);

        for(int i=0;i<ans;i++)

            printf("%c%d",i==0?'
':' ',res[i]);

        printf("
");

    }

    return 0;

}