HDU 1709 The Balance [母函数]

谁践踏了优雅 2022-05-30 12:41 155阅读 0赞

# The Balance #

##### Time Limit : 1000/1000ms (Java/Other)   Memory Limit : 32768/32768K (Java/Other) #####

##### Total Submission(s) : 13   Accepted Submission(s) : 6 #####

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

#include <stdio.h>
    #include <string.h> 
    int main(int argc, char *argv[])
    {
    	int c1[100005],c2[100005];
    	int count[1005],num[1005];
    	int n,i,j,k;
    	int counts,sum;
    	while(scanf("%d",&n)!=EOF)
    	{
    		sum=0;
    		counts=0;
    		memset(c1,0,sizeof(c1));
    		memset(c2,0,sizeof(c2));
    		for(i=1;i<=n;i++)
    			scanf("%d",&num[i]),
    			sum+=num[i];
    		c1[0]=1;	
    		c1[num[1]]=1;	
    		for(i=2;i<=n;i++)
    		{
    			for(j=0;j<=sum;j++)
    				for(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[k+j]+=c1[j];	
    				}
    				for(j=0;j<=sum;j++)
    					c1[j]=c2[j],c2[j]=0;
    		}		
    		for(i=1,j=0;i<=sum;i++)
    		{
    			if(c1[i]==0)
    			{
    				counts+=1;
    				count[j++]=i;
    			}	
    		}
    		if(counts==0)
    			printf("0\n");
    		else
    		{
    			printf("%d\n",counts);
    			for(i=0;i<counts-1;i++)
    				printf("%d ",count[i]);
    			printf("%d\n",count[counts-1]);
    		}
    	}	
    	return 0;
    }