hdu 2082 找單詞（母函數）

找單詞

Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4971 Accepted Submission(s): 3537


Problem Description 假設有x1個字母A， x2個字母B,..... x26個字母Z，同時假設字母A的價值為1，字母B的價值為2,..... 字母Z的價值為26。那麼，對於給定的字母，可以找到多少價值<=50的單詞呢？單詞的價值就是組成一個單詞的所有字母的價值之和，比如，單詞ACM的價值是1+3+14=18，單詞HDU的價值是8+4+21=33。(組成的單詞與排列順序無關，比如ACM與CMA認為是同一個單詞）。

Input 輸入首先是一個整數N，代表測試實例的個數。
然後包括N行數據，每行包括26個<=20的整數x1,x2,.....x26.

Output 對於每個測試實例，請輸出能找到的總價值<=50的單詞數,每個實例的輸出占一行。
Sample Input

2
1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
9 2 6 2 10 2 2 5 6 1 0 2 7 0 2 2 7 5 10 6 10 2 10 6 1 9

Sample Output

7
379297

Source

2006/1/15 ACM程序設計期末考試

母函數模板，有變形，多多理解，我把我理解的都注釋希望小伙伴能懂

如果有哪點理解的不對，望大神指出
2015,7,28

 

#include
#include
int a[30],x[55],y[55];
int main()
{
	int t,i,j,k;
	scanf("%d",&t);
	while(t--){
		memset(x,0,sizeof(x));//x數組存放的是各項單詞組合價值不大於50的組合數 
		memset(y,0,sizeof(y));//y數組存放中間一次的情況 
		for(i=1;i<=26;i++)
			scanf("%d",&a[i]);
		for(i=0;i<51 && i<=a[1];i++)//值為1的個數 
			x[i]=1;//如果只用值為1的數就可以表示值i，那麼x[i]就初始化為1 
			
		for(i=2;i<=26;i++){//i表示第i個表達式 ，上邊1已經存過，所以從2開始 
			for(j=0;j<=50;j++){//j表示前邊i個表達式累成後的表達式裡的第j個變量 
				for(k=0;k+j<=50 && k<=a[i]*i;k+=i)//k表示第i個的指數 
					y[k+j]+=x[j];//i這個指數最多有a[i]個，所以k最大是a[i]*i 
			}
			for(j=0;j<51;j++){
				x[j]=y[j];
				y[j]=0;
			}
		}
		int sum=0;
		for(i=1;i<=50;i++)
			sum+=x[i]; 
		printf("%d\n",sum);
	}
	return 0;
}