1、動(dòng)態(tài)規(guī)劃及其應(yīng)用,賴國(guó)堃 福建師大附中,基本概念,動(dòng)態(tài)規(guī)劃問題的滿足兩個(gè)基本性質(zhì) 一、最優(yōu)子結(jié)構(gòu) 問題可以表示為一些子問題，然后通過求解子問題的最優(yōu)答案，得到問題答案。 二、無后效性 當(dāng)前決策不會(huì)影響到之后的決策。,動(dòng)態(tài)規(guī)劃的3個(gè)基本要素,狀態(tài) 轉(zhuǎn)移 邊界 這3個(gè)一般是做動(dòng)態(tài)規(guī)劃時(shí)要先思考清楚的問題。,例題,例1、數(shù)字三角形 （圖2）示出了一個(gè)數(shù)字三角形。 請(qǐng)編一個(gè)程序計(jì)算從頂至底的某處的一條路徑，使該路徑所經(jīng)過的數(shù)字的總和最大。 每一步可沿左斜線向下或右斜線向下走； 1三角形行數(shù)100； 三角形中的數(shù)字為整數(shù)0，1，99； 輸入數(shù)據(jù)： 由INPUT.TXT文件中首先讀到的是三角形的行數(shù)。 在

2、例子中INPUT.TXT表示如下： 5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 輸出數(shù)據(jù)： 把最大總和（整數(shù)）寫入OUTPUT.TXT文件。 上例為： 30,分析,只要對(duì)該題稍加分析，就可以得出一個(gè)結(jié)論： 如果得到一條由頂至底的某處的一條最佳路徑，那么對(duì)于該路徑上的每一個(gè)中間點(diǎn)來說，由頂至該中間點(diǎn)的路徑所經(jīng)過的數(shù)字和也為最大。因此該題是一個(gè)典型的多階段決策最優(yōu)化的問題。 我們采用動(dòng)態(tài)規(guī)劃中的順推解法。按三角形的行劃分階段。若行數(shù)為n, 則可把問題看作一個(gè)n-1個(gè)階段的決策問題。從始點(diǎn)出發(fā)，依順序求出第一階段、第二階段，第n-1階段中各決策點(diǎn)至始點(diǎn)的最佳路徑，最終求出始點(diǎn)到終

3、點(diǎn)的最佳路徑。,狀態(tài)：fI,j表示，走到第i行第j列最大得分 轉(zhuǎn)移：fI,j=fi-1,j-1+cI,j(j1) =fI-1,j+cI,j(ji),For i := 2 to N Do For j := 1 to i Do Begin Listi, j.Tot := -1; 從1,1至i,j的數(shù)字和初始化 If (j 1) And (Listi - 1, j - 1.Tot + Listi, j.Val Listi, j.Tot) Then Listi, j.Tot := Listi - 1, j - 1.Tot + Listi, j.Val; 若從i-1,j-1選擇右斜線向下會(huì)使1,1至i,

4、j的數(shù)字和最 大,則決策該步 If (j i) And (Listi - 1, j.Tot + Listi, j.Val Listi, j.Tot) Then Listi, j.Tot := Listi - 1, j.Tot + Listi, j.Val 若從i-1,j選擇左斜線向下會(huì)使1,1至i,j的數(shù)字和最大,則決策該步 End; for,例題,有一個(gè)體積為V背包，現(xiàn)在有n個(gè)物品，他們格子有自己的體積vi，和各自的價(jià)值wi?，F(xiàn)在需要選出一些物品裝進(jìn)背包，你的任務(wù)是使裝進(jìn)物品的價(jià)值最大。,狀態(tài)：fI,j(i表示處理第幾個(gè)物品，j表示已用了多大空間) 轉(zhuǎn)移：fI,j=max(fi-1,j-vi

5、+ci,fi-1,j) 邊界：f0,0=0;,for i:=1 to n do for j:=1 to m do begin if j=vi then fi,j:=max(fi-1,j-vi+ci,fi-1,j) else fi,j:=fi-1,j; end;,例題,【問題描述】 假設(shè)以最美觀的方式布置花店的櫥窗，有F束花，每束花的品種都不一樣，同時(shí)，至少有同樣數(shù)量的花瓶，被按順序擺成一行，花瓶的位置是固定的，并從左到右，從1到V順序編號(hào)，V 是花瓶的數(shù)目，編號(hào)為1的花瓶在最左邊，編號(hào)為V的花瓶在最右邊，花束可以移動(dòng)，并且每束花用1到F 的整數(shù)惟一標(biāo)識(shí)，標(biāo)識(shí)花束的整數(shù)決定了花束在花瓶中列的順序

6、即如果I J，則花束I 必須放在花束J左邊的花瓶中。 例如，假設(shè)杜鵑花的標(biāo)識(shí)數(shù)為1，秋海棠的標(biāo)識(shí)數(shù)為2，康乃馨的標(biāo)識(shí)數(shù)為3，所有的花束在放入花瓶時(shí)必須保持其標(biāo)識(shí)數(shù)的順序，即：杜鵑花必須放在秋海棠左邊的花瓶中，秋海棠必須放在康乃馨左邊的花瓶中。如果花瓶的數(shù)目大于花束的數(shù)目，則多余的花瓶必須空，即每個(gè)花瓶中只能放一束花。,每一個(gè)花瓶的形狀和顏色也不相同，因此，當(dāng)各個(gè)花瓶中放入不同的花束時(shí)會(huì)產(chǎn)生不同的美學(xué)效果，并以美學(xué)值(一個(gè)整數(shù))來表示，空置花瓶的美學(xué)值為0。在上述例子中，花瓶與花束的不同搭配所具有的美學(xué)值，可以用如下表格表示。比如杜鵑花放在花瓶2中，會(huì)顯得非常好看，但若放在花瓶4中則顯得很難看。

7、,為取得最佳美學(xué)效果，必須在保持花束順序的前提下，使花的擺放取得最大的美學(xué)值，如果具有最大美學(xué)值的擺放方式不止一種，則輸出任何一種方案即可。題中數(shù)據(jù)滿足下面條件：1F100，F(xiàn)V100，50AIJ50，其中AII是花束I擺放在花瓶J中的美學(xué)值。輸入整數(shù)F，V 和矩陣(AIJ)，輸出最大美學(xué)值和每束花擺放在各個(gè)花瓶中的花瓶編號(hào)。,【輸入文件】 第一行包含兩個(gè)數(shù)：F，V。 隨后的F 行中，每行包含V 個(gè)整數(shù)，Aij 即為輸入文件中第（i+1 ）行中的第j 個(gè)數(shù) 【輸出文件】 包含兩行:第一行是程序所產(chǎn)生擺放方式的美學(xué)值。第二行必須用F 個(gè)數(shù)表示擺放方式，即該行的第K個(gè)數(shù)表示花束K所在的花瓶的編號(hào)。

8、 【輸入樣例】 3 5 7 23 5 24 16 5 21 -4 10 23 -21 5 -4 -20 20 【輸出樣例】 53 2 4 5,方法1,既然要拿花束一個(gè)一個(gè)的放，我們就以花束劃分階段。在這里，階段變量k表示的就是要布置的花束數(shù)目（前k束花），狀態(tài)變量sk表示第k束花所在的花瓶。而對(duì)于每一個(gè)狀態(tài)sk，決策就是第k-1束花應(yīng)該放在哪個(gè)花瓶，用uk表示。最優(yōu)指標(biāo)函數(shù)fk(sk)表示前k束花，其中第k束插在第sk個(gè)花瓶中，所能取得的最大美學(xué)值。,規(guī)劃方程為： （其中A(i,j)是花束i插在花瓶j中的美學(xué)值） fI,j=max(fi-1,u+aI,j)(i=uj),方法2,以花瓶的數(shù)目來劃

9、分階段。在這里階段變量k表示的是要占用的花瓶數(shù)目（前k個(gè)花瓶），狀態(tài)變量sk表示前k個(gè)花瓶中放了多少花。而對(duì)于任意一個(gè)狀態(tài)sk，決策就是第sk束花是否放在第k個(gè)花瓶中，用變量uk=1或0來表示。最優(yōu)指標(biāo)函數(shù)fk(sk)表示前k個(gè)花瓶中插了sk束花，所能取得的最大美學(xué)值。 規(guī)劃方程為：fI,j=max(fi-1,j,fi-1,j-1+aj,i),區(qū)間類動(dòng)態(tài)規(guī)劃,（1）石子合并 【問題描述】 在一個(gè)圓形操場(chǎng)的四周擺放著n 堆石子?，F(xiàn)要將石子有次序地合并成一堆。規(guī)定每次只能選相鄰的2 堆石子合并成新的一堆，并將新的一堆石子數(shù)記為該次合并的得分。 試設(shè)計(jì)一個(gè)算法，計(jì)算出將n堆石子合并成一堆的最小得分和

10、最大得分。 【輸入文件】包含兩行，第1 行是正整數(shù)n（1=n=100），表示有n堆石子。第2行有n個(gè)數(shù)，分別表示每堆石子的個(gè)數(shù)。 【輸出文件】輸出兩行。 第1 行中的數(shù)是最小得分；第2 行中的數(shù)是最大得分。 【輸入樣例】44 4 9 5 【輸出樣例】4354,分析 看到本題，容易想到使用貪心法，即每次選取相鄰最大或最小的兩堆石子合并。 然而這樣做對(duì)不對(duì)呢？看一個(gè)例子。 6 3 4 6 5 4 2 如果使用貪心法求最小得分，應(yīng)該是如下的合并步驟： 第一次合并 3 4 6 5 4 2 2,3合并得分是 第二次合并 5 4 6 5 4 5,4合并得分是9 第三次合并 9 6 5 4 5,4合并得分是

11、9 第四次合并 9 6 9 9,6合并得分是15 第五次合并 15 9 15,9合并得分是24 總得分599152462但是如果采用如下合并方法，卻可以得到比上面得分更少的方法： 第一次合并 3 4 6 5 4 2 3,4合并得分是7 第二次合并 7 6 5 4 2 7,6合并得分是13 第三次合并 13 5 4 2 4,2合并得分是6 第四次合并 13 5 6 5,6合并得分是11 第五次合并 13 11 13,11合并得分是24 總得分7136112461 顯然，貪心法是錯(cuò)誤的。 為什么？ 顯然，貪心只能導(dǎo)致局部的最優(yōu)，而局部最優(yōu)并不導(dǎo)致全局最優(yōu)。,具體來說我們應(yīng)該定義一個(gè)數(shù)組si,j用來

12、表示合并方法，i表示從編號(hào)為第i堆的石頭開始合并，j表示從i開始數(shù)j堆進(jìn)行合并，si,j為合并的最優(yōu)得分。 則動(dòng)規(guī)方程為： SI,j=minsI,k+si+k,j-k+sumI,j 1=k=j-1 2=j=n 邊界：sI,1=0;,由此得到算法框架如下： For j2 to n do 枚舉階段，從兩兩合并開始計(jì)算 For i1 to n do 計(jì)算當(dāng)前階段的n種不同狀態(tài)的值 For k1 to j-1 do 枚舉不同的分段方法 begin If i+kn then t(i+k) mod n else ti+k 最后一個(gè)連第一個(gè)的情況處理 si,j最優(yōu)si,k+st,j-k+sum1,3 sum

13、i,j表示從i開始數(shù)j個(gè)數(shù)的和 end;,在Mars星球上，每個(gè)Mars人都隨身佩帶著一串能量項(xiàng)鏈。在項(xiàng)鏈上有N顆能量珠。能量珠是一顆有頭標(biāo)記與尾標(biāo)記的珠子，這些標(biāo)記對(duì)應(yīng)著某個(gè)正整數(shù)。并且，對(duì)于相鄰的兩顆珠子，前一顆珠子的尾標(biāo)記一定等于后一顆珠子的頭標(biāo)記。因?yàn)橹挥羞@樣，通過吸盤（吸盤是Mars人吸收能量的一種器官）的作用，這兩顆珠子才能聚合成一顆珠子，同時(shí)釋放出可以被吸盤吸收的能量。如果前一顆能量珠的頭標(biāo)記為m，尾標(biāo)記為r，后一顆能量珠的頭標(biāo)記為r，尾標(biāo)記為n，則聚合后釋放的能量為（Mars單位），新產(chǎn)生的珠子的頭標(biāo)記為m，尾標(biāo)記為n。 需要時(shí)，Mars人就用吸盤夾住相鄰的兩顆珠子，通過聚合得

14、到能量，直到項(xiàng)鏈上只剩下一顆珠子為止。顯然，不同的聚合順序得到的總能量是不同的，請(qǐng)你設(shè)計(jì)一個(gè)聚合順序，使一串項(xiàng)鏈釋放出的總能量最大。 例如：設(shè)N=4，4顆珠子的頭標(biāo)記與尾標(biāo)記依次為(2，3)(3，5)(5，10)(10，2)。我們用記號(hào)表示兩顆珠子的聚合操作，(jk)表示第j，k兩顆珠子聚合后所釋放的能量。則第4、1兩顆珠子聚合后釋放的能量為： (41)=10*2*3=60。 這一串項(xiàng)鏈可以得到最優(yōu)值的一個(gè)聚合順序所釋放的總能量為 (41)2)3）=10*2*3+10*3*5+10*5*10=710。,【輸入文件】 輸入文件energy.in的第一行是一個(gè)正整數(shù)N（4N100），表示項(xiàng)鏈上珠子

15、的個(gè)數(shù)。第二行是N個(gè)用空格隔開的正整數(shù)，所有的數(shù)均不超過1000。第i個(gè)數(shù)為第i顆珠子的頭標(biāo)記（1iN），當(dāng)i時(shí)，第i顆珠子的尾標(biāo)記應(yīng)該等于第i+1顆珠子的頭標(biāo)記。第N顆珠子的尾標(biāo)記應(yīng)該等于第1顆珠子的頭標(biāo)記。 至于珠子的順序，你可以這樣確定：將項(xiàng)鏈放到桌面上，不要出現(xiàn)交叉，隨意指定第一顆珠子，然后按順時(shí)針方向確定其他珠子的順序。 【輸出文件】 輸出文件energy.out只有一行，是一個(gè)正整數(shù)E（E2.1*109），為一個(gè)最優(yōu)聚合順序所釋放的總能量。 【輸入樣例】 4 23510 【輸出樣例】 710,算法分析,如果要求一個(gè)鏈的最優(yōu)合并方式,可以把這個(gè)鏈從中間斷開,枚舉斷開處,分別求出2段的

16、最優(yōu)合并的值,再將這兩端合并,而這條鏈斷開后的2段的最優(yōu)合并方式也可以用同樣的方式計(jì)算,因此,本題具有最優(yōu)子結(jié)構(gòu)性質(zhì),可以用動(dòng)態(tài)規(guī)劃求解 但本題中并不是一個(gè)鏈而是一個(gè)環(huán),但這并不影響最優(yōu)子結(jié)構(gòu)性質(zhì),可以做一條鏈,長(zhǎng)度是環(huán)的2倍,其中前半段與后半段一樣,都為環(huán)的順序(可任意確定),那么,從中間任取長(zhǎng)度為n的一段,就實(shí)現(xiàn)了環(huán)的性質(zhì)首尾相接,設(shè)fk,j為從珠子k到珠子j的最優(yōu)合并,那么枚舉斷開點(diǎn)p,則fk,j的最優(yōu)值為fk,p的最優(yōu)值和fp+1,j的最優(yōu)值的和再加珠子k,p和p+1,j合并的值vk(k的頭標(biāo)記)*vp+1(p的尾標(biāo)記=p+1的頭標(biāo)記)*vj+1(即j的尾標(biāo)記) 動(dòng)規(guī)方程為:fk,j=

17、maxfk,p+fp+1,j+vk*vp+1*vj+1 (kj2*n且k=pj),for d=1 to n /從小到大枚舉鏈的長(zhǎng)度 for k=1 to 2*n do /枚舉鏈的起點(diǎn) begin j=k+d-1;/計(jì)算鏈的終點(diǎn) if(j=2*n)/若在最大值范圍內(nèi) for p=k to j-1 /枚舉斷開點(diǎn)begin 根據(jù)方程更新fk,j的值;end;end;,例題,1、加分二叉樹（noip2003） 【問題描述】 設(shè)一個(gè)n個(gè)節(jié)點(diǎn)的二叉樹tree的中序遍歷為（l,2,3,n），其中數(shù)字1,2,3,n為節(jié)點(diǎn)編號(hào)。每個(gè)節(jié)點(diǎn)都有一個(gè)分?jǐn)?shù)（均為正整數(shù)），記第i個(gè)節(jié)點(diǎn)的分?jǐn)?shù)為di，tree及它的每個(gè)子樹

18、都有一個(gè)加分，任一棵子樹subtree（也包含tree本身）的加分計(jì)算方法如下： subtree的左子樹的加分 subtree的右子樹的加分subtree的根的分?jǐn)?shù) 若某個(gè)子樹為空，規(guī)定其加分為1，葉子的加分就是葉節(jié)點(diǎn)本身的分?jǐn)?shù)。不考慮它的空子樹。 試求一棵符合中序遍歷為（1,2,3,n）且加分最高的二叉樹tree。要求輸出； （1）tree的最高加分 （2）tree的前序遍歷,【輸入格式】 第1行：一個(gè)整數(shù)n（n30），為節(jié)點(diǎn)個(gè)數(shù)。 第2行：n個(gè)用空格隔開的整數(shù)，為每個(gè)節(jié)點(diǎn)的分?jǐn)?shù)（分?jǐn)?shù)100）。 【輸出格式】 第1行：一個(gè)整數(shù)，為最高加分（結(jié)果不會(huì)超過4,000,000,000）。 第2行：

19、n個(gè)用空格隔開的整數(shù)，為該樹的前序遍歷。 【輸入樣例】 5 5 7 1 2 10 【輸出樣例】 145 3 1 2 4 5,如果整棵樹的權(quán)值最大，必然有左子樹的權(quán)值最大，右子樹的權(quán)值也最大，符合最優(yōu)性原理 本題適合用動(dòng)態(tài)規(guī)劃來解。如果用數(shù)組fi,j表示從節(jié)點(diǎn)i到節(jié)點(diǎn)j所組成的二叉樹的最大加分，枚舉根節(jié)點(diǎn)，則動(dòng)態(tài)方程可以表示如下： fi,j=maxi=t=j | dt+fi,t-1*ft+1,j 初始： f(i,i)=di 目標(biāo)：f(1,n),procedure dfs(l,r:integer); var i:integer; s:int64; begin if fl,r0 then exit;

20、/實(shí)現(xiàn)記憶化 if l=r then /處理邊界 begin fl,r:=al; dl,r:=l; exit; end;,for i:=l to r do begin s:=0; if i-l0 then begin dfs(l,i-1);s:=fl,i-1;end;/處理左子樹的加分 if r-i0 then begin dfs(i+1,r);if s0 then s:=s*fi+1,r else s:=fi+1,r;end; inc(s,ai); if sfl,r then begin fl,r:=s; dl,r:=i; end; end; end;,樹形動(dòng)態(tài)規(guī)劃,顧名思義，樹型動(dòng)態(tài)規(guī)劃就

21、是在“樹”的數(shù)據(jù)結(jié)構(gòu)上的動(dòng)態(tài)規(guī)劃，平時(shí)作的動(dòng)態(tài)規(guī)劃都是線性的或者是建立在圖上的，線性的動(dòng)態(tài)規(guī)劃有二種方向既向前和向后，相應(yīng)的線性的動(dòng)態(tài)規(guī)劃有二種方法既順推與逆推，而樹型動(dòng)態(tài)規(guī)劃是建立在樹上的，所以也相應(yīng)的有二個(gè)方向： 1、根葉：不過這種動(dòng)態(tài)規(guī)劃在實(shí)際的問題中運(yùn)用的不多，也沒有比較明顯的例題，所以不在今天討論的范圍之內(nèi)。 2、葉根：既把根的子節(jié)點(diǎn)傳遞有用的信息給根，完成后根得出最優(yōu)解的過程。這類的習(xí)題比較的多，下面就介紹一些這類題目和它們的一般解法。（樹的后序遍歷求解）,2、Ural 1018二叉蘋果樹 【問題描述】 有一棵蘋果樹，如果樹枝有分叉，一定是分2叉（就是說沒有只有1個(gè)兒子的結(jié)點(diǎn)）這棵

22、樹共有N個(gè)結(jié)點(diǎn)（葉子點(diǎn)或者樹枝分叉點(diǎn)），編號(hào)為1-N,樹根編號(hào)一定是1。 我們用一根樹枝兩端連接的結(jié)點(diǎn)的編號(hào)來描述一根樹枝的位置。下面是一顆有4個(gè)樹枝的樹 2 5 / 3 4 / 1 現(xiàn)在這顆樹枝條太多了，需要剪枝。但是一些樹枝上長(zhǎng)有蘋果。給定需要保留的樹枝數(shù)量，求出最多能留住多少蘋果。 輸入格式 第1行2個(gè)數(shù)，N和Q(1=Q= N,1N=100)。 N表示樹的結(jié)點(diǎn)數(shù)，Q表示要保留的樹枝數(shù)量。接下來N-1行描述樹枝的信息。 每行3個(gè)整數(shù)，前兩個(gè)是它連接的結(jié)點(diǎn)的編號(hào)。第3個(gè)數(shù)是這根樹枝上蘋果的數(shù)量。 每根樹枝上的蘋果不超過30000個(gè)。 輸出格式 一個(gè)數(shù)，最多能留住的蘋果的數(shù)量。,樣例輸入 5

23、21 3 11 4 102 3 203 5 20 樣例輸出 21,分析： 因?yàn)轭}目一給出就是純二叉的樹結(jié)構(gòu)，如果要保留住最多蘋果數(shù)量，必然是左子樹保留盡量多，右子樹也保留盡量多，滿足最優(yōu)性原理,我們定義狀態(tài),fi,j表示以i為根的子樹(還包括 i與 i的父親 這條邊)內(nèi),保存j條邊最多可以有多少蘋果,顯然fi,j=max(flefti,k+frighti,j-k-1)+applei,fatheri; （0=k=j-1） 邊界：f0,i=0;fi,0=0; 問題的解：f1,q+1;虛擬了一條邊，也就相當(dāng)于多添加了一個(gè)節(jié)點(diǎn)1的父親節(jié)點(diǎn)，這條邊為1和它父親節(jié)點(diǎn)的,procedure tree_dp(

24、t,k:integer); var i,ls,rs:integer; begin if ft,k0 then exit; if (t=0) or (k=0) then begin ft,k:=0; exit; end; ft,k:=0; for i:=0 to k-1 do begin tree_dp(treet.lc,i);/左子樹 tree_dp(treet.rc,k-i-1);/右子樹 ls:=ftreet.lc,i;/記錄左子樹的值 rs:=ftreet.rc,k-i-1;/記錄右子樹的值 if ft,kls+rs then ft,k:=ls+rs;/比較 end; ft,k:=ft,

25、k+treet.s; /保存最優(yōu)值 end;,例題,問題描述 在大學(xué)里每個(gè)學(xué)生，為了達(dá)到一定的學(xué)分，必須從很多課程里選擇一些課程來學(xué)習(xí)，在課程里有些課程必須在某些課程之前學(xué)習(xí)，如高等數(shù)學(xué)總是在其它課程之前學(xué)習(xí)?，F(xiàn)在有N門功課，每門課有個(gè)學(xué)分，每門課有一門或沒有直接先修課（若課程a是課程b的先修課即只有學(xué)完了課程a，才能學(xué)習(xí)課程b）。一個(gè)學(xué)生要從這些課程里選擇M門課程學(xué)習(xí)，問他能獲得的最大學(xué)分是多少？ 輸入： 第一行有兩個(gè)整數(shù)N,M用空格隔開。(1=N=200,1=M=150) 接下來的N行,第I+1行包含兩個(gè)整數(shù)ki和si, ki表示第I門課的直接先修課，si表示第I門課的學(xué)分。若ki=0表示

26、沒有直接先修課（1=ki=N, 1=si=20）。 輸出： 只有一行，選M門課程的最大得分。,樣例：,分析,根據(jù)先修關(guān)系，選修的課程組成了一個(gè)森林，我們虛擬一個(gè)根節(jié)點(diǎn)0作為這棵森林的總根 然后我們把一棵普通樹轉(zhuǎn)化為二叉樹進(jìn)行求解。 讀入數(shù)據(jù)時(shí)把二叉樹建好：第一個(gè)孩子作為父節(jié)點(diǎn)的左子樹，其它孩子作為第一個(gè)孩子的右子樹。 F（i，j）：表示節(jié)點(diǎn)以i為根結(jié)點(diǎn)取j門課的最高學(xué)分，則,F(leftc,k)：表示左子樹選了k門課的最大學(xué)分。 F(rightc,j)：表示右子樹選了j門課的最大學(xué)分。 Fleftc,k+frightc,j-k-1+si：表示左子樹選了k門，當(dāng)然選了左子樹，必須選根，右子樹選了

27、j-k-1門。 其實(shí)是四種情況決策：(1) 選右子樹中j門（2）選左子樹（j-1）門+根 （3）選右子樹（j-1門）+根 （4）選左子樹（k門）+根+選右子樹（j-k-1） 程序中節(jié)點(diǎn)1表示空節(jié)點(diǎn)，0是根節(jié)點(diǎn)，1n是n門可選課程的節(jié)點(diǎn).,源程序代碼： program bluewater; type tree=record l,r,k:longint; end; var s:string; i,j,k,l:longint; n,m:longint; a:array0.200 of tree;/存儲(chǔ)樹的信息 b:array-1.200,0.150 of integer;/狀態(tài)表示 f:array0

28、.200 of longint;/存父親節(jié)點(diǎn),procedure treedp(x,y:longint); var i,j,k,l:longint; begin if bx,y=0 then exit; treedp(ax.r,y);只有右子樹的情況 j:=bax.r,y; for k:=1 to y do左右子樹都有的情況 begin treedp(ax.l,k-1); treedp(ax.r,y-k); i:=bax.l,k-1+bax.r,y-k+ax.k; if ij then j:=i; end; bx,y:=j; end;,begin readln(s); assign(input

29、,s);reset(input); readln(n,m); fillchar(f,sizeof(f),0); for i:=0 to n do begin ai.l:=-1;ai.r:=-1;ai.k:=-1;end; 建樹 for i:=1 to n do begin readln(k,l); ai.k:=l; if fk=0 then ak.l:=i else afk.r:=i; fk:=i; end;,邊界 for i:=-1 to n do for j:=-1 to m do if (i=-1) or (j=0) then bi,j:=0 else bi,j:=-1; 記憶化實(shí)現(xiàn)動(dòng)規(guī)

30、 treedp(a0.l,m); 輸出 writeln(ba0.l,m); end. 時(shí)間復(fù)雜度最大為O(n3) 思考:若本題加上選那些課程可得到這個(gè)最大學(xué)分,怎樣修改程序？,4、 河流(IOI2005) 一顆有N+1個(gè)結(jié)點(diǎn)的樹，樹中的每個(gè)結(jié)點(diǎn)可能會(huì)生產(chǎn)出一些產(chǎn)品。這些產(chǎn)品要么就地加工（要有加工廠才行），要么運(yùn)送到它的父親結(jié)點(diǎn)那兒去?，F(xiàn)在在整棵樹的根結(jié)點(diǎn)處已經(jīng)有了一個(gè)產(chǎn)品加工廠，而且所有的產(chǎn)品最終必須在某個(gè)加工廠加工才行。由于運(yùn)費(fèi)昂貴，不可能將所有的產(chǎn)品都運(yùn)送到根節(jié)點(diǎn)處加工?，F(xiàn)在決定在樹中的某些結(jié)點(diǎn)新增總共K個(gè)加工廠，現(xiàn)在要你選擇這K個(gè)加工廠的廠址。 假設(shè)結(jié)點(diǎn)i會(huì)生產(chǎn)出Wi噸產(chǎn)品，它的父結(jié)點(diǎn)是

31、Pi。而它到它的父結(jié)點(diǎn)的路徑的長(zhǎng)度是Ui。運(yùn)費(fèi)的計(jì)算是每運(yùn)送1頓的貨物，每單位長(zhǎng)度收取1的費(fèi)用。根節(jié)點(diǎn)的編號(hào)為0。,例如下圖，0節(jié)點(diǎn)是根節(jié)點(diǎn)，如果要新增兩個(gè)工廠，最佳方案是建在2、3兩個(gè)節(jié)點(diǎn)上，這樣總的費(fèi)用為： 1*1（1號(hào)）+1*3（4號(hào)）=4,分析：由于題目中給出的樹是多叉樹，不便于進(jìn)行動(dòng)態(tài)規(guī)劃。我們先利用兒子兄弟表示法，將多叉樹轉(zhuǎn)化為二叉樹 進(jìn)行了相關(guān)的轉(zhuǎn)化之后，設(shè)f(i,j,k)表示在新樹中，以i結(jié)點(diǎn)為根的子樹中，分配k個(gè)加工廠。并且離i結(jié)點(diǎn)最近的加工廠在j結(jié)點(diǎn)的情況下。i結(jié)點(diǎn)及其子樹內(nèi)的所有產(chǎn)品，加工所需要的費(fèi)用。 轉(zhuǎn)移方程很容易就可以寫出來： 總時(shí)間復(fù)雜度為O(N2K2)。,狀態(tài)壓

32、縮動(dòng)態(tài)規(guī)劃,有一些問題卻被認(rèn)為很可能不存在有效的(多項(xiàng)式級(jí)的)算法，這里以對(duì)幾個(gè)例題的剖析，簡(jiǎn)述狀態(tài)壓縮思想及其應(yīng)用。,預(yù)備知識(shí),引例,在n*n(n20)的方格棋盤上放置n個(gè)車(可以攻擊所在行、列)，求使它們不能互相攻擊的方案總數(shù)。,分析,其實(shí)本題是一個(gè)簡(jiǎn)單的組合數(shù)學(xué)問題，因?yàn)槊啃杏星覂H有一個(gè)車，所以我們只要來考慮每行上列的問題，顯然每列只能出現(xiàn)一次，這題答案就是n的一個(gè)全排列，為 P(n,n)=n! 當(dāng)然這題還有狀態(tài)壓縮的解法。,分析,我們?nèi)匀灰恍幸恍蟹胖谩?取棋子的放置情況作為狀態(tài)，某一列如果已經(jīng)放置棋子則為1，否則為0。這樣，一個(gè)狀態(tài)就可以用一個(gè)最多20位的二進(jìn)制數(shù)表示。 例如n=5,第

33、1、3、4列已經(jīng)放置，則這個(gè)狀態(tài)可以表示為01101(從右到左)。設(shè)fs為達(dá)到狀態(tài)s的方案數(shù)，則可以嘗試建立f的遞推關(guān)系。,前兩行在第3、4列放置了棋子(不考慮順序，下同)，第三行在第1列放置； 前兩行在第1、4列放置了棋子，第三行在第3列放置； 前兩行在第1、3列放置了棋子，第三行在第4列放置。,這三種情況互不相交，且只可能有這三種情況，根據(jù)加法原理，fs應(yīng)該等于這三種情況的和。 根據(jù)上面的討論思路推廣之，得到引例的解決辦法： 其中s的右起第i+1位為1 (其實(shí)就是在枚舉s的二進(jìn)制表示中的1),狀態(tài)壓縮具有良好的拓展性。 在n*n(n20)的方格棋盤上放置n個(gè)車，某些格子不能放，求使它們不能

34、互相攻擊的方案總數(shù)。 我們只需要在原題的程序中枚舉添加1的位置的時(shí)候進(jìn)行判斷就行。,program p1; const max=1 shl 20; var n,i,t,c,j,tmp,r:longint; f,a:array0.maxof int64; begin assign(input,p1.in);a reset(input); readln(n); fillchar(f,sizeof(f),0); for i:=1 to n do /讀入及預(yù)處理 begin ai:=0; for j:=1 to n do /如果第i行的某位為0,表示這位不能放置 begin read(c); ai:=ai shl 1; if c=1 then ai:=ai+1; end; end;,f0:=1; for i:=1 to (1 shl n)-1 do begin t:=i; r:=0; while t0 do /計(jì)算狀態(tài)i中1的個(gè)數(shù)，即可得到其為第幾行 begin inc(r); t:=t-(t and -t); end; tmp:=i and ar