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

9 2 1

Sample Output

2

4 5

Source

HDU 2007-Spring Programming Contest

Recommend

lcy

每种砝码既可以放在右盘，又可以放在左盘，（若按左物右码来说），放在左盘那就取减号，放在右盘就取加号。

题意：

一个天平，若干个砝码，给你每个砝码的重量，问你不能用这个天平和砝码称量出什么重量？砝码可以放在天平的左右两边的哟。

题解：

母函数，砝码模型，套模板，具体见算法归纳的母函数。虽然我想这么说，不过这次是变种，直接套模板就哭了。因为砝码可以两边放，所以加多一条代码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?'\n':' ',res[i]);
        printf("\n");
    }
    return 0;
}