1、歷屆NOIp動態(tài)規(guī)劃梳理,動態(tài)規(guī)劃(dynamic programming)是運籌學的一個分支，是求解決策過程最優(yōu)化的數(shù)學方法。動態(tài)規(guī)劃算法把多階段過程轉(zhuǎn)化為一系列單階段問題，利用各階段之間的關(guān)系，逐個求解，以得到全局最優(yōu)策略。 動態(tài)規(guī)劃是信息學競賽中選手必須熟練掌握的一種算法,它以其多元性廣受出題者的喜愛。近年來，動態(tài)規(guī)劃幾乎每次都出現(xiàn)在NOIp的賽場上，而且還有越來越多的趨勢。因此，掌握基本的NOIp動態(tài)規(guī)劃題是至關(guān)重要的。,動態(tài)規(guī)劃實質(zhì)：,枚舉,+,遞推,狀態(tài),狀態(tài)轉(zhuǎn)移方程,Sample Problem1,1,3,5,9,1,從樹的根到樹的葉節(jié)點，最多能取多少數(shù)？,貪心：答案錯誤,暴力搜

2、索：如果數(shù)據(jù)大會超時,動態(tài)規(guī)劃！,我們先將NOIp里的動態(tài)規(guī)劃分分類：,最長不降子序列 背包 方格取數(shù) 石子歸并 狀態(tài)壓縮 數(shù)學遞推 順序遞推,最長不降子序列,設有由n個不相同的整數(shù)組成的數(shù)列，記為: a(1)、a(2)、a(n)且a(i)a(j) (i，j=n) 例如3，18，7，14，10，12，23，41，16，24。 若存在i1i2i3 ie 且有a(i1)a(i2) a(ie)則稱為長度為e的不下降序列。如上例中3，18，23，24就是一個長度為4的不下降序列，同時也有3，7，10，12，16，24長度為6的不下降序列。最長的不下降序列就是求長度最長的子序列。 For i:=1 To

3、 n Do For j:=1 To i-1 Do If (ai=aj)And(fifj+1) Then fi:=fj+1;,合唱隊形（NOIp2004） 【問題描述】 N位同學站成一排，音樂老師要請其中的(N-K)位同學出列，使得剩下的K位同學排成合唱隊形。 合唱隊形是指這樣的一種隊形：設K位同學從左到右依次編號為1，2，K，他們的身高分別為T1，T2，TK，則他們的身高滿足T1Ti+1TK(1=i=K)。 你的任務是，已知所有N位同學的身高，計算最少需要幾位同學出列，可以使得剩下的同學排成合唱隊形。 【輸入文件】 輸入文件第一行是一個整數(shù)N(2=N=100)，表示同學的總數(shù)。第一行有n個整數(shù)

4、，用空格分隔，第i個整數(shù)Ti(130=Ti=230)是第i位同學的身高。 【輸出文件】 輸出文件包括一行，這一行只包含一個整數(shù)，就是最少需要幾位同學出列。,Sample Problem2,最長不降子序列,最長不降子序列,最長不降子序列,最長不降子序列,依此類推,最長不降子序列,攔截導彈（NOIp1999） 某國為了防御敵國的導彈襲擊，發(fā)展出一種導彈攔截系統(tǒng)。但是這種導彈攔截系統(tǒng)有一個缺陷：雖然它的第一發(fā)炮彈能夠到達任意的高度，但是以后每一發(fā)炮彈都不能高于前一發(fā)的高度。某天，雷達捕捉到敵國的導彈來襲。由于該系統(tǒng)還在試用階段，所以只有一套系統(tǒng)，因此有可能不能攔截所有的導彈。 輸入導彈依次飛來的高度

5、（雷達給出的高度數(shù)據(jù)是不大于30000的正整數(shù)），計算這套系統(tǒng)最多能攔截多少導彈，如果要攔截所有導彈最少要配備多少套這種導彈攔截系統(tǒng)。 樣例： INPUT OUTPUT 389 207 155 300 299 170 158 65 6（最多能攔截的導彈數(shù)） 2（要攔截所有導彈最少要配備的系統(tǒng)數(shù)）,Sample Problem3,最長不降子序列,第一問：最長下降子序列。,第二問：DP？,反例： 9 8 7 1 10 6 5 4,最長不降子序列,9 8 7 1 10 6 5 4,DP：,9 8 7 1 10 6 5 4,1 10,1 10,10,10,3次！,最長不降子序列,9 8 7 1 10

6、6 5 4,貪心：,2次！,9 8 7 1 10 6 5 4,10 6 5 4,DP不是萬能的！,10 6 5 4,背包,01背包：有N件物品和一個容量為V的背包。第i件物品的費用是ci，價值是wi。求解將哪些物品裝入背包可使價值總和最大。 完全背包：有N種物品和一個容量為V的背包，每種物品都有無限件可用。第i種物品的費用是ci，價值是wi。求解將哪些物品裝入背包可使這些物品的費用總和不超過背包容量，且價值總和最大。 For i:=1 To n Do For j:=Max Downto ai Do (ai To Max) If fjfj-ai+bi Then fj:=fj-ai+bi;,背包,

7、Sample Problem4,金明的預算方案（NOIp2006） 【問題描述】 金明今天很開心，家里購置的新房就要領(lǐng)鑰匙了，新房里有一間金明自己專用的很寬敞的房間。更讓他高興的是，媽媽昨天對他說：“你的房間需要購買哪些物品，怎么布置，你說了算，只要不超過N元錢就行”。今天一早，金明就開始做預算了，他把想買的物品分為兩類：主件與附件，附件是從屬于某個主件的。如果要買歸類為附件的物品，必須先買該附件所屬的主件。每個主件可以有0個、1個或2個附件。附件不再有從屬于自己的附件。金明想買的東西很多，肯定會超過媽媽限定的N元。于是，他把每件物品規(guī)定了一個重要度，分為5等：用整數(shù)15表示，第5等最重要。他

8、還從因特網(wǎng)上查到了每件物品的價格（都是10元的整數(shù)倍）。他希望在不超過N元（可以等于N元）的前提下，使每件物品的價格與重要度的乘積的總和最大。 設第j件物品的價格為vj，重要度為wj，共選中了k件物品，編號依次為j1，j2，jk，則所求的總和為： vj1*wj1+vj2*wj2+ +vjk*wjk。（其中*為乘號） 請你幫助金明設計一個滿足要求的購物單。,背包,Sample Problem4,【輸入文件】 第1行，為兩個正整數(shù)N m（其中N（0，表示該物品為附件，q是所屬主件的編號） 【輸出文件】 只有一個正整數(shù)，為不超過總錢數(shù)的物品的價格與重要度乘積的總和的最大值?！据斎霕永?1000 5

9、 800 2 0 400 5 1 300 5 1 400 3 0 500 2 0 【輸出樣例】 2200,背包,For i:=1 To n Do For j:=m Downto ai Do If fj-ai-1 then Begin 00 If fj-ai+bifj Then fj:=fj-ai+bi; Ff:=fj-ai+bi; 01 If j+si,1,1fj+si,1,1 Then fj+si,1,1:=Ff+si,1,2; 10 If j+si,2,1fj+si,2,1 Then fj+si,2,1:=Ff+si,2,2; 11 If j+si,1,1+si,2,1fj+si,1,1+

10、si,2,1 Then fj+si,1,1+si,2,1:=Ff+si,1,2+si,2,2; End; End;,背包,Sample Problem5,郵票面值設計（NOIp1999） 給定一個信封，最多只允許粘貼N張郵票，計算在給定K（N+K40）種郵票的情況下（假定所有的郵票數(shù)量都足夠），如何設計郵票的面值，能得到最大值MAX，使在1MAX之間的每一個郵資值都能得到。 例如，N=3，K=2，如果面值分別為1分、4分，則在1分6分之間的每一個郵資值都能得到（當然還有8分、9分和12分）；如果面值分別為1分、3分，則在1分7分之間的每一個郵資值都能得到?？梢则炞C當N=3，K=2時，7分就是可

11、以得到的連續(xù)的郵資最大值，所以MAX=7，面值分別為1分、3分。 【樣例】 INPUT N=3 K=2 OUTPUT 1 3 MAX=7,背包,如果你一看到這道題目就想到搜索，那么,恭喜你，你答對了！,方格取數(shù),Sample Problem6,方格取數(shù) （NOIp2000） 設有N*N的方格圖(N=10,我們將其中的某些方格中填入正整數(shù),而其他的方格中則放入數(shù)字0。如下圖所示某人從圖的左上角的A 點出發(fā)，可以向下行走，也可以向右走，直到到達右下角的B點。在走過的路上，他可以取走方格中的數(shù)（取走后的方格中將變?yōu)閿?shù)字0）。 此人從A點到B 點共走兩次，試找出2條這樣的路徑，使得取得的數(shù)之和為最大。

12、,方格取數(shù),13+14+4+21+15=67,方格取數(shù),一取方格數(shù)：fi,j:=maxfi-1,j,fi,j-1; 現(xiàn)在要做的數(shù)二取方格數(shù)，是否還能像一取方格數(shù)那樣如法炮制呢？,答案是肯定的！,我們觀察一下它的路徑。fi,j是從fi-1,j或者fi,j-1走來。無論是從fi-1,j還是fi,j-1走來，要么是x坐標+1，要么是y坐標+1，總歸x坐標的值+y坐標的值一定比前一個多1。 我們來驗證一下：,方格取數(shù),X坐標（3，3） 3+3=6 Y坐標（3，4） 3+4=7 Z坐標（4，4） 4+4=8,方格取數(shù),再觀察，我們發(fā)現(xiàn)，走第n步時，能走到點是固定的。觀察其坐標我們發(fā)現(xiàn)，第n步能走到的點其

13、坐標和為n-1。,因此，走到第n步時，x坐標和y坐標的和就知道=n+1，這樣我們就不必同時知道2條路線x坐標和y坐標了，知道其中一個t，另外一個就可以用n+1-t來表示了。,于是此題迎刃而解！,方格取數(shù),用fx,i,j表示走到第x步時，第1條路線走到橫坐標為i的地方，第2條路線走到了橫坐標為j的地方。這樣，我們只要枚舉x，i，j，就能遞推出來了。,For x:=3 To m+n Do For i:=1 To Min(x,n) Do For j:=1 To Min(x,n) Do Begin fx,i,j:=Max(fx-1,i,j,fx-1,i-1,j,fx-1,i,j-1,fx-1,i-1,

14、j-1); If i=j Then Inc(fx,i,j,ai,x-i) Else Begin Inc(fx,i,j,ax-i,i); Inc(fx,i,j,ax-j,j); End; End;,同樣三取方格數(shù)只要fx,i,j,k用同樣的方法即可。,方格取數(shù),傳紙條（NOIp2008） 【問題描述】 小淵和小軒是好朋友也是同班同學，他們在一起總有談不完的話題。一次素質(zhì)拓展活動中，班上同學安排做成一個m行n列的矩陣，而小淵和小軒被安排在矩陣對角線的兩端，因此，他們就無法直接交談了。幸運的是，他們可以通過傳紙條來進行交流。紙條要經(jīng)由許多同學傳到對方手里，小淵坐在矩陣的左上角，坐標(1,1)，小軒坐

15、在矩陣的右下角，坐標(m,n)。從小淵傳到小軒的紙條只可以向下或者向右傳遞，從小軒傳給小淵的紙條只可以向上或者向左傳遞。 在活動進行中，小淵希望給小軒傳遞一張紙條，同時希望小軒給他回復。班里每個同學都可以幫他們傳遞，但只會幫他們一次，也就是說如果此人在小淵遞給小軒紙條的時候幫忙，那么在小軒遞給小淵的時候就不會再幫忙。反之亦然。 還有一件事情需要注意，全班每個同學愿意幫忙的好感度有高有低（注意：小淵和小軒的好心程度沒有定義，輸入時用0表示），可以用一個0-100的自然數(shù)來表示，數(shù)越大表示越好心。小淵和小軒希望盡可能找好心程度高 的同學來幫忙傳紙條，即找到來回兩條傳遞路徑，使得這兩條路徑上同學 的

16、好心程度只和最大?，F(xiàn)在，請你幫助小淵和小軒找到這樣的兩條路徑。,Sample Problem7,石子歸并,Sample Problem8,石子歸并原題 【題目描述】 在一個圓形操場的四周擺放著N堆石子(N= 100),現(xiàn)要將石子有次序地合并成一堆.規(guī)定每次只能選取相鄰的兩堆合并成新的一堆,并將新的一堆的石子數(shù),記為該次合并的得分.編一程序,由文件讀入堆棧數(shù)N及每堆棧的石子數(shù)(=20). 選擇一種合并石子的方案,使用權(quán)得做N1次合并,得分的總和最小。 【輸入數(shù)據(jù)】 第一行為石子堆數(shù)N; 第二行為每堆的石子數(shù),每兩個數(shù)之間用一個空格分隔。 【輸出數(shù)據(jù)】 一行，最小總和。 【輸入】44 5 9 4

17、【輸出】22,石子歸并,4,5,9,4,石子歸并,我們用fi,j表示以i堆石子為開頭，以j堆石子為結(jié)尾的一系列石子歸并起來的最小總和。 因為題目中說，只能歸并相鄰的兩堆石子。所以，fi,j這一系列石子必然由fi,k和fk+1,j（i=kj）這兩堆石子歸并而來。只要在所有的fi,k+fk+1,j中取個最小值（就是原來此次沒歸并前的最小值），加上自己本身所有石子的和（因為歸并一次的代價是所有石子的總和），就是我們要求的fi,j。 因此，狀態(tài)轉(zhuǎn)移方程為：,而fi,i和一段石子的總和是可以預處理的，只要將石子序列倍長，復雜度O(n3)，此題就能順利AC了。,石子歸并,For i:=1 To n-1 D

18、o For j:=1 To 2*n-i Do Begin fj,j+i:=Maxlongint; For k:=j To j+i Do If fj,j+ifj,k+fk+1,j+i Then fj,j+i:=fj,k+fk+1,j+i; fj,j+i:=fj,j+i+Sumj,j+i; End; 這樣，求歸并的最大值也是同樣的方法，不再贅述。,石子歸并,Sample Problem9,能量項鏈（NOIp2006） 在Mars星球上，每個Mars人都隨身佩帶著一串能量項鏈。在項鏈上有N顆能量珠。能量珠是一顆有頭標記與尾標記的珠子，這些標記對應著某個正整數(shù)。并且，對于相鄰的兩顆珠子，前一顆珠子的尾

19、標記一定等于后一顆珠子的頭標記。因為只有這樣，通過吸盤（吸盤是Mars人吸收能量的一種器官）的作用，這兩顆珠子才能聚合成一顆珠子，同時釋放出可以被吸盤吸收的能量。如果前一顆能量珠的頭標記為m，尾標記為r，后一顆能量珠的頭標記為r，尾標記為n，則聚合后釋放的能量為（Mars單位），新產(chǎn)生的珠子的頭標記為m，尾標記為n。 需要時，Mars人就用吸盤夾住相鄰的兩顆珠子，通過聚合得到能量，直到項鏈上只剩下一顆珠子為止。顯然，不同的聚合順序得到的總能量是不同的，請你設計一個聚合順序，使一串項鏈釋放出的總能量最大。 例如：設N=4，4顆珠子的頭標記與尾標記依次為(2，3) (3，5) (5，10) (10

20、，2)。我們用記號表示兩顆珠子的聚合操作，(jk)表示第j，k兩顆珠子聚合后所釋放的能量。則第4、1兩顆珠子聚合后釋放的能量為(41)=10*2*3=60。 這一串項鏈可以得到最優(yōu)值的一個聚合順序所釋放的總能量為 (41)2)3）=10*2*3+10*3*5+10*5*10=710。,石子歸并,Sample Problem10,乘積最大（NOIp2000） 【問題描述】 設有一個長度為N的數(shù)字串，要求選手使用K個乘號將它分成K+1個部分，找出一種分法，使得這K+1個部分的乘積能夠為最大。 【輸入】 程序的輸入共有兩行： 第一行共有2個自然數(shù)N，K（6N40，1K6） 第二行是一個長度為N的數(shù)字

21、串。 【輸出】 輸出所求得的最大乘積（一個自然數(shù)）。 【樣例輸入】 4 2 1231 【樣例輸出】 62,石子歸并,這道題目要求把一個長度為n的數(shù)字串分成k段，使得每段的乘積最大。 通過剛才的石子歸并思想，我們可以用fi,j表示前i個數(shù)字我分了j段所能得到的最大值，那么fi,j就可以從fk,j-1（前k個數(shù)字分成了j-1段）推來，因為fi,j就是fk,j-1和（k+1i）這段數(shù)字串的乘積。 于是狀態(tài)轉(zhuǎn)移方程即可得出： fi,j:=Maxfk,j-1*Numberk+1,i (j-1=ki) 其中Numberk+1,j表示數(shù)字串從第k+1位到第i位轉(zhuǎn)換成數(shù)字的值。 對于題目中所說的具有很強枚舉意

22、味的變量（如k段，n次等），一般將其放入狀態(tài)中枚舉。而諸如最大值最小值之類的變量，一般放入數(shù)組中作為值遞推。,Sample Problem11,統(tǒng)計單詞個數(shù)（NOIp2001） 【問題描述】 給出一個長度不超過200的由小寫英文字母組成的字母串(約定;該字串 以每行20個字母的方式輸入，且保證每行一定為20個)。要求將此字母串分 成k份(1k=40)，且每份中包含的單詞個數(shù)加起來總數(shù)最大(每份中包含的單詞可以部分重疊。當選用一個單詞之后，其第一個字母不能再用。 例如字符串this中可包含this和is，選用this之后就不能包含th)。單詞在給出 的一個不超過6個單詞的字典中。要求輸出最大的個

23、數(shù)。 【樣例輸入】 3 thisisabookyouareaoh 4 is a ok sab 【樣例輸出】 7 this / isabookyoua / reaoh,石子歸并,石子歸并,看到這道題目應該馬上有這種意識了：和乘積最大神似！ 所以本題除了求出ij之間有多少單詞以外基本上就沒什么難度了。預處理出ij之間有多少單詞，其實也可以用DP。 首先，題目告訴我們，如果a是b的前綴，那么b肯定沒用了（為什么）。所以第一步刪串。之后的任務就是求單詞數(shù)了。令si,j表示ij之間有多少個單詞，那么si,j=si,j-1+以第j位為結(jié)尾，包含在ij這段串里的單詞個數(shù)。 如串cabce，單詞有cab、ab

24、c。明顯第13之間有1個單詞，而14之間呢？13有的它肯定也有，再去枚舉單詞中有沒有是cabc后綴的單詞。最終f1,4=f1,3+1。,Sample Problem12,矩陣取數(shù)游戲（NOIp2007） 【問題描述】 帥帥經(jīng)常更同學玩一個矩陣取數(shù)游戲：對于一個給定的n*m的矩陣，矩陣中的每個元素aij據(jù)為非負整數(shù)。游戲規(guī)則如下： 1. 每次取數(shù)時須從每行各取走一個元素，共n個。m次后取完矩陣所有元素； 2. 每次取走的各個元素只能是該元素所在行的行首或行尾； 3. 每次取數(shù)都有一個得分值，為每行取數(shù)的得分之和；每行取數(shù)的得分 = 被取走的元素值*2i，其中i表示第i次取數(shù)（從1開始編號）； 4

25、. 游戲結(jié)束總得分為m次取數(shù)得分之和。 帥帥想請你幫忙寫個程序，對于任意矩陣，可以求出取數(shù)后的最大得分。 【輸入】 第一行為兩個用空格隔開的整數(shù)n和m。 第2n+1行為n*m矩陣，其中每行有m個用單個空格隔開 【輸出】 一個整數(shù)，即輸入矩陣取數(shù)后的最大的分。 【限制】 60%的數(shù)據(jù)滿足：1=n, m=30，答案不超過106 100%的數(shù)據(jù)滿足：1=n, m=80，0=aij=1000,石子歸并,改變一下題目的敘述：每行有m個數(shù)，倒數(shù)第i次取的得分是ai*2(m+1-i)；倒推，因為每次只能取一段中的頭或尾，所以剩下的永遠是連續(xù)的一段，每次加入頭或尾。 把一段的頭和尾看做一堆石子，把ai*2(m

26、+1-i)看做每次歸并的加分，每次歸并不是取相鄰的，而是取一段中的頭或尾就是石子歸并。 用fi,j,k表示第i行，取了一些數(shù)后剩下連續(xù)的一段從j到k，那么狀態(tài)轉(zhuǎn)移方程就很好寫了： fi,j,k:=Maxfi,j-1,k+aj-1*2(m-k+j-1) fi,j,k+1+ak+1*2(m-k+j-1); 這道題目還要高精度，建議寫好非高精的DP再修 改成高精度的。,石子歸并,狀態(tài)壓縮,過河（NOIp2005） 【問題描述】 在河上有一座獨木橋，一只青蛙想沿著獨木橋從河的一側(cè)跳到另一側(cè)。在橋上有一些石子，青蛙很討厭踩在這些石子上。由于橋的長度和青蛙一次跳過的距離都是正整數(shù)，我們可以把獨木橋上青蛙可

27、能到達的點看成數(shù)軸上的一串整點：0，1，L（其中L是橋的長度）。坐標為0的點表示橋的起點，坐標為L的點表示橋的終點。青蛙從橋的起點開始，不停的向終點方向跳躍。一次跳躍的距離是S到T之間的任意正整數(shù)（包括S,T）。當青蛙跳到或跳過坐標為L的點時，就算青蛙已經(jīng)跳出了獨木橋。 題目給出獨木橋的長度L，青蛙跳躍的距離范圍S,T，橋上石子的位置。你的任務是確定青蛙要想過河，最少需要踩到的石子數(shù)。 【輸入文件】 第一行一個正整數(shù)L（1 = L = 109），表示獨木橋的長度。第二行有三個正整數(shù)S，T，M，分別表示青蛙一次跳躍的最小距離，最大距離，及橋上石子的個數(shù)，其中1 = S = T = 10，1 =

28、M = 100。第三行有M個不同的正整數(shù)分別表示這M個石子在數(shù)軸上的位置（數(shù)據(jù)保證橋的起點和終點處沒有石子）。所有相鄰的整數(shù)之間用一個空格隔開。 【輸出文件】 一個整數(shù)，表示青蛙過河最少需要踩到的石子數(shù)。,Sample Problem13,狀態(tài)壓縮,此題乍一看上去好像很簡單，因為只要沿著青蛙跳的方向，逐步遞推即可。大致代碼如下： For i:=1 To L+t-1 Do（仔細想想為什么？） For j:=s To t Do If i這個位子有石頭 Then If fifi-j+1 Then fi:=fi-j+1 Else If fifi-j Then fi:=fi-j; 但是有個地方我們忽略了

29、，那就是數(shù)據(jù)規(guī)模。L最大有109，第一個For就已經(jīng)無法承受龐大的時間限制和空間限制了。所以，這種方法需要進行改進。而改進的方法，就是狀態(tài)壓縮。,狀態(tài)壓縮,我們可以發(fā)現(xiàn)題目的一個玄機：雖然L很大，但是M卻很小，也就是說：,石子很稀疏,石子稀疏對我們解題有什么幫助呢？我們來看一下下面的推斷：,第一種情況： 當s=t時，很簡單，青蛙踩到的石頭肯定是s的倍數(shù)，那么只要統(tǒng)計一下所有石子中有多少是s的倍數(shù)，輸出即可。,第二種情況：st 我們先來看一組數(shù)據(jù)。s=4，t=5。,從數(shù)據(jù)中我們看到，12以后的點全部都是可以到達的了。如果s=4，t=5，在一段100000的距離中沒有石頭，其實12以后的點都是不用

30、遞推就知道肯定能到達的。那么我們用原始的方法做就會浪費很大的資源。 所以當s=4，t=5時，如果一段沒有石頭的區(qū)間長度在4*5=20以外，那么我們只要遞推前20就可以了，因為20后面的情況是一樣的（仔細想想為什么？）。,狀態(tài)壓縮,假設s=3，t=5，那么11=3+4+4就也可以到達了。所以，只有當t=s+1時，連續(xù)的點的起始位置才能盡量后面。最壞情況就是s=9，t=10了（仔細想想為什么？）。 跟前面的s=4，t=5的情況一樣，其實s=9，t=10時只要一段沒有石頭的區(qū)間長度在90之外，我們都把它當做90對待就可以了。 因此，我們每次對于一段沒有石頭的區(qū)間長度為x，如果xt(t-1)時，我們就

31、把它當做t(t-1)處理。這樣，最大的復雜度就是t(t-1)*（石頭個數(shù)+1）=90*101=9090，比之前的復雜度大大降低。 這種方法叫狀態(tài)壓縮，我們這題用的方法叫離散 化。至此，過河完美AC！,狀態(tài)壓縮,Sample Problem14,數(shù)的劃分（NOIp2001） 【問題描述】 將整數(shù)n分成k份，且每份不能為空，任意兩份不能相同(不考慮順序)。例如：n=7，k=3，下面三種分法被認為是相同的。 1，1，5; 1，5，1; 5，1，1; 問有多少種不同的分法。 【輸入】 n，k (6n=200，2=k=6)【輸出】 一個整數(shù)，即不同的分法。 【樣例】 輸入： 7 3 輸出： 4 四種分法

32、為：1，1，5；1，2，4；1，3，3；2，2，3；,數(shù)學遞推,應該明確這是一道數(shù)學題，數(shù)學題往往有明顯或暗藏的規(guī)律可以快速求得解。在NOIp中數(shù)學遞推題并不常見，但不能排除它出現(xiàn)的可能性。對于這類問題，我們不能盲目找規(guī)律，而要細細尋找每個狀態(tài)之間的內(nèi)在聯(lián)系，從而一步一步求得最終要求的答案。此類問題一般要用到數(shù)學公式、數(shù)學證明、方程變形、極端化等思想，根據(jù)題目的不同適當選取方法。 根據(jù)前面講的，有幾個枚舉量我們就設幾個狀態(tài)，這道題目明顯n和k都是枚舉量，要求的幾種方案是值，因此建立起遞推狀態(tài)：fi,j表示將i分成j份的方案數(shù)。 接下來就是寫出狀態(tài)轉(zhuǎn)移方程了，一旦狀態(tài)轉(zhuǎn)移方程寫出，那么fi,j就

33、可以由fx,y等其他狀態(tài)得來，因為得到最后我們要求得fn,k。,數(shù)學遞推,數(shù)學遞推,我們先來看一下f10,4的幾種分割方法，如圖：可以看見10=1+1+3+5=1+2+3+4=2+2+3+3。乍一看我們沒發(fā)現(xiàn)什么規(guī)律，但是這些分割方法都有一個共同點：,每種分割方法所分割 出來的小整數(shù)都=1!,因為不允許出 現(xiàn)10=0+10這 種分割，所以,數(shù)學遞推,有了這個性質(zhì)，我們來嘗試下面的操作：將所有小整數(shù)都減去1。,這樣，f10,4就被改成了f6,2、f6,3、f6,4等小狀態(tài)。通過類推，小狀態(tài)可以分成更小的狀態(tài)。,一般地，fi,j就可以分成fi-j,1、fi-j,2、fi-j,3等小狀態(tài)，而fi,j

34、的種數(shù)就是小狀態(tài)的總合。,fi,j:=fi-j,1+fi-j,2+fi-j,3+fi-j,j-1+fi-j,j;,數(shù)學遞推,知道了遞推公式，我們就可以推得fn,k。 For i:=1 To n Do For j:=1 To k Do If i=j Then For t:=1 To j Do fi,j:=fi,j+fi-j,t; 時間復雜度是你n*k2的。雖然可以輕松過這題，但如果n=50000，k=200，這樣的方法就超時了。所以我們要精益求精：這題還有O(n*k)的方法。 觀察下面的變形：,fi,j:=fi-j,1+fi-j,2+fi-j,j;,數(shù)學遞推,fi-1,j-1:=f(i-1)-(j-1),1+f(i-1)-(j-1),2f(i-1)-(j-1),j-1,=fi-j,1+fi-j,2+fi-j,j-1;, fi,j:=fi-j,1+fi-j,2+fi-j,j-1+fi-j,j,=fi-1,j-1+fi-j,j;,這樣，遞推就成了n*k的了,For i:=1 To n Do For j:=1 To k Do If i=j Then fi,j:=fi-1,j-1+fi-j,j;,最后加點預處理，此題完美就AC了！ 反思：解決此類題目，必先學好數(shù)學！,Sample Problem15,加分二叉樹（NOIp2003） 【問題描述】 設一個n