母函数解决 Jam's balance hdu5616

2019-11-08 02:47:10

字体：大中小

来源：转载

供稿：网友

Jam's balance

Time Limit: 2000/1000 MS (java/Others) Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 1572 Accepted Submission(s): 669PRoblem DescriptionJim has a balance and N weights. (1≤N≤20)The balance can only tell whether things on different side are the same weight.Weights can be put on left side or right side arbitrarily.Please tell whether the balance can measure an object of weight M. InputThe first line is a integer T(1≤T≤5), means T test cases.For each test case :The first line is N, means the number of weights.The second line are N number, i'th number wi(1≤wi≤100) means the i'th weight's weight is wi.The third line is a number M. M is the weight of the object being measured. OutputYou should output the "YES"or"NO". Sample Input

121 43245 Sample OutputNOYESYESHintFor the Case 1:Put the 4 weight aloneFor the Case 2:Put the 4 weight and 1 weight on both side  
题母的 意思是  给 几个砝码    砝码 可以放在天平的 两边 或者一边 ，  问你 给你几个 测试数据 砝码 能否 恰好 称出 这个数据 
这个 题 解法有多种  ， 我用的母函数 ： 
模板一：
//1.0：母函数 解决 模板一 #include<stdio.h>#include<stdlib.h>#include<string.h>#define abs(x) ((x)<0? -(x):(x))// - 一定要在（）外 int a[2015],b[2015];int v[2015];int main(){	int T,n,m;	int i,j,k,kk;	while(~scanf("%d",&T))	{		while(T--)		{			int sum=0;			memset(v,0,sizeof(v));//清零操作			memset(a,0,sizeof(a));			memset(b,0,sizeof(b));			scanf("%d",&n);			for(i=1;i<=n;i++)			{				scanf("%d",&v[i]);				sum+=v[i];			}			a[v[1]]=a[0]=1;//初始 化  			for(i=2;i<=n;i++)//次数 			{				memset(b,0,sizeof(b)); //╮(╯_╰)╭进行一次 就  初始为0 				for(j=0;j<=sum;j++)// 每个 v[]  				{					for(k=0;k+j<=sum&&k<=v[i];k+=v[i])//每个a 					{						b[k+j]+=a[j];//天平一边 						b[abs(k-j)]+=a[j];//天平两边 					}				}				memcpy(a,b,sizeof(b));				}				scanf("%d",&m);//			printf("abs=%d/n",abs(5-6));//			for(i=0;i<sum;i++)//				{//					printf("%d /n",a[i]);//				//				}			while(m--)			{				scanf("%d",&kk);				if(a[kk])				{					printf("YES/n");				}				else				{					printf("NO/n");				}			}				}	}	return 0;}