母函數解決 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;}