找單詞Time Limit: 1000/1000 MS (java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 7007 Accepted Submission(s): 4887PRoblem 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輸入首先是一個整數(shù)N，代表測試實例的個數(shù)。然后包括N行數(shù)據(jù)，每行包括26個<=20的整數(shù)x1,x2,.....x26. Output對于每個測試實例，請輸出能找到的總價值<=50的單詞數(shù),每個實例的輸出占一行。 Sample Input21 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 09 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 Output7379297一開始我想著這道題大概可以用背包問題解決，但擔心可能枚舉情況過多最后導致超時。于是百度了一下題解，發(fā)現(xiàn)了一個新的名詞母函數(shù)。母函數(shù)據(jù)網(wǎng)上所言分為普通母函數(shù)和指數(shù)母函數(shù)。在此題上只用使用普通母函數(shù)。 普通母函數(shù)可以用于解決“帶價值及數(shù)量的復數(shù)種類物品，從中取出固定價值的方案數(shù)”問題。在此題中我們可以枚舉固定價值1-50從而求出小于等于50的價值單詞取法數(shù)量。母函數(shù)解決此類問題的原理在于多項式乘法底數(shù)相乘指數(shù)相加的特性，而這剛好貼合于組合問題。比如你同時取出了價值1,2,3的三個種類物品各一件，此時你手中的價值為6 ，用多項式乘法就表示為x^1*x^2*x^3=x^6，此時x的六次方的六就代表著取出這三個物件后的價值。而且我們都知道多項式乘法時，某一多項式的每一項都會與另一多項式的每一項相乘。于是我們就能構造一種取與不取的形式。假設現(xiàn)在有價值1,2,3的三個種類物品各一件，問你能取出多少種價值，每種價值有多少種取法。在之前的例子時，x的某次方參與計算代表取了他，那么不取明顯就是1，也就是大多數(shù)人所說的x^0，那么用(1+x^1)*(1+x^2)*(1+x^3)這個式子就能表達三個物品取或不取的全部情況，計算結果是1+x^1+x^2+x^3+x^4+x^5+x^6，則說明可以取出1-6這六種價值情況，而且每種情況的可能情況都是1。通過以上的知識就可以求出“從帶價值及數(shù)量的復數(shù)種類物品中取固定價值的方案數(shù)”以下是代碼：#include<stdio.h>int main(){ int c1[51],c2[51],num[27],n,i,j,k; scanf("%d",&n); while(n--){ for(i=0;i<=51;i++){ c1[i]=0; c2[i]=0; } for(i=1;i<=26;i++) scanf("%d",&num[i]); c1[0]=1; for(i=1;i<=26;i++){ for(j=0;j<=50;j++) for(k=0;k<=num[i];k++) if(j+k*i<=50) c2[j+k*i]+=c1[j]; else break; for(int j=0;j<=50;j++){ c1[j]=c2[j]; c2[j]=0; } } int ans=0; for(i=1;i<=50;i++) ans+=c1[i]; printf("%d/n",ans); }} |
新聞熱點
疑難解答
