Description

假設(shè)有x1個(gè)字母A， x2個(gè)字母B,..... x26個(gè)字母Z，同時(shí)假設(shè)字母A的價(jià)值為1，字母B的價(jià)值為2,..... 字母Z的價(jià)值為26。那么，對(duì)于給定的字母，可以找到多少價(jià)值<=50的單詞呢？單詞的價(jià)值就是組成一個(gè)單詞的所有字母的價(jià)值之和，比如，單詞ACM的價(jià)值是1+3+14=18，單詞HDU的價(jià)值是8+4+21=33。(組成的單詞與排列順序無(wú)關(guān)，比如ACM與CMA認(rèn)為是同一個(gè)單詞）。???????

Input

輸入首先是一個(gè)整數(shù)N，代表測(cè)試實(shí)例的個(gè)數(shù)。??????? 然后包括N行數(shù)據(jù)，每行包括26個(gè)<=20的整數(shù)x1,x2,.....x26.???????

Output

對(duì)于每個(gè)測(cè)試實(shí)例，請(qǐng)輸出能找到的總價(jià)值<=50的單詞數(shù),每個(gè)實(shí)例的輸出占一行。??????

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 這類(lèi)題也就能夠很明晰的做出來(lái)了，就兩個(gè)字“暴力” ，雖說(shuō)這個(gè)詞不怎么招人喜歡，但是如何暴力，怎樣暴力確實(shí)一大知識(shí)點(diǎn)，DFS、BFS不都是暴力嗎，但還是很受歡迎，母函數(shù)就是一個(gè)有章可依，有模板可套的暴力。 1 #include<stdio.h> 2 #include<string.h> 3 4 int le[30],n1[55],n2[55]; 5 6 void GF( ) 7 { 8 memset(n1,0,sizeof(n1)); 9 memset(n2,0,sizeof(n2)); 10 n1[0]=1; //在上一篇報(bào)告里面講過(guò)其作用，可以說(shuō)是一個(gè)入口 11 for(int i=1;i<=26;++i) 12 { 13 for(int j=0;j<=50;++j) 14 // j從0開(kāi)始還是為了保留未參與合并的原值 15 for(int k=0;k<=le[i]&&k*i+j<=50;k++) 16 // k從0開(kāi)始是為了保留n1[x]中原有的值，不至于在 17 // 后面n1[x]=n2[x]語(yǔ)句中出現(xiàn)n1[x]數(shù)據(jù)丟失。 18 n2[j+k*i]+=n1[j]; // 這和前面的判斷是否存在（只需賦值 為1）組合不同 19 for(int j=0;j<=50;++j) 20 { 21 n1[j]=n2[j]; // k從0開(kāi)始保證了n1[x]只增不減 22 n2[j]=0; 23 } 24 } 25 } 26 27 int main() 28 { 29 int T; 30 scanf("%d",&T); 31 while(T--) 32 { 33 int cnt=0; 34 for(int i=1;i<=26;++i) 35 scanf("%d",&le[i]); 36 GF(); 37 for(int i=1;i<=50;++i) // 題目是要統(tǒng)計(jì)小于50的所有可能 38 cnt+=n1[i]; 39 printf("%d\n",cnt); 40 } 41 return 0; 42 }

把 “Lvsi”開(kāi)的初級(jí)母函數(shù)DIY 都做完了,由于中間看了背包，經(jīng)常是腦袋里面一團(tuán)混亂，尤其是HDU 1171，唉，又能用母函數(shù)，又能用多重背包。所以急忙寫(xiě)點(diǎn)解題報(bào)告，清理清理下自己的思路。? 對(duì)母函數(shù)而言，在做題中，用到了它的兩種用法，一種可以說(shuō)是原型的變形（簡(jiǎn)化）。

其一：用來(lái)模擬組合問(wèn)題，最經(jīng)典莫過(guò)于 錢(qián)幣兌換 了，有1-N 種幣值的硬幣，如拿M元紙幣兌換，問(wèn)有多少種兌換方式，母函數(shù)就是統(tǒng)計(jì)頻數(shù)（或其他變量）的啟發(fā)函數(shù)，其核心 語(yǔ)句 是 n1[j+k]+=n2[j];?

n1[x]--這個(gè)數(shù)組就是存儲(chǔ)頻數(shù)的，一般如果你換10元 這個(gè)數(shù)組在循環(huán)中的界值就為10，

n2[x]--這個(gè)是用來(lái)做臨時(shí)儲(chǔ)存用的，把一次合并操作中相同值的數(shù)加起來(lái)，且每次加的是n1[x]（值暫不變）而不是加自身。

j--錢(qián)幣的組合值，n1[j] 就是組成 j 元錢(qián)的方案數(shù)。

k--這個(gè)就是當(dāng)前參與組合的錢(qián)幣的動(dòng)態(tài)值，比如一次操作中是將 6枚價(jià)值為10的硬幣組合進(jìn)去，那么k<0.10...60>，在每次的操作中是這樣的，當(dāng)k=0時(shí)，n2[j]=n1[j],這樣剛好能夠?qū)1[j]的原值過(guò)渡過(guò)來(lái)，當(dāng)k=10時(shí)，n2[j+10]的值是在原來(lái)的基礎(chǔ)上在加上n1[j],因?yàn)檫@里的一枚價(jià)值為 10? 硬幣確實(shí)能夠和?已經(jīng)能夠組合成的錢(qián)幣數(shù) j? 組成 j+10的組合，而這種組合的的頻數(shù)N=P*1；P為原頻數(shù)?, P=n1[j]。而后的k取值則按照類(lèi)似的關(guān)系進(jìn)行。???

其二：用來(lái)枚舉所有可能的組合，不要求 求出頻數(shù)，只需統(tǒng)計(jì)是否可能存在，就像上一篇報(bào)告中遇到的題目，給你一定要求的錢(qián)幣只有價(jià)值為 1、2、5 的錢(qián)幣各若干枚，題中給出三個(gè)數(shù)代表各個(gè)錢(qián)幣的數(shù)量，問(wèn)你用這些錢(qián)幣組合錢(qián)幣中從1開(kāi)始，最小的不能組合成的錢(qián)幣數(shù)值。 因此此題中無(wú)需統(tǒng)計(jì)組合后某一數(shù)目值出現(xiàn)了多少次，統(tǒng)計(jì)也是多此一舉。其核心 語(yǔ)句為：
if(n1[j])???n2[j+k]=1;? 意思是說(shuō)如果 前組合值值存在，那么當(dāng)前組合值存在。

轉(zhuǎn)載于:https://www.cnblogs.com/wangmengmeng/p/4552565.html

總結(jié)

以上是生活随笔為你收集整理的找单词（母函数问题）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。