動態(tài)程序設(shè)計朱全民

1、動態(tài)程序設(shè)計動態(tài)程序設(shè)計朱全民基本原理1、多階段最優(yōu)化決策：、多階段最優(yōu)化決策：即由初始狀態(tài)開始，通過對中間階段決策的選擇，達到結(jié)束狀態(tài)。這些決策形成了一個決策序列，同時確定了完成整個過程的一條最優(yōu)的活動路線。帶權(quán)有向的多段圖 上一階段的狀態(tài)下一階段的狀態(tài)決策概念w 狀態(tài)狀態(tài)（State）：表示事物的性質(zhì)，是描述“動態(tài)規(guī)劃”中的“單元”的量。亦是每一階段求解過程的出發(fā)點。w 階段階段（Stage）：階段是一些性質(zhì)相近，可以同時處理同時處理的狀態(tài)集合，或者說，階段只是標(biāo)識那些處理方法相同、處理順序無關(guān)的狀態(tài)。w 決策決策（Decision）：每個階段做出的某種選擇性的行動，是程序所需要完成的選擇

2、。w 狀態(tài)轉(zhuǎn)移方程：狀態(tài)轉(zhuǎn)移方程：是前一個階段的狀態(tài)轉(zhuǎn)移到后一個的狀態(tài)的演變規(guī)律，是關(guān)于兩個相鄰階段狀態(tài)變化的方程，是“動態(tài)規(guī)劃”的中心。設(shè)設(shè) fk(i)k階段狀態(tài)i的最優(yōu)權(quán)值，即初始狀態(tài)至狀態(tài)i的最優(yōu)代價 fk+1(i)=minxk(j)+u(i,j) 基本原理w 最優(yōu)性原理作為整個過程的最優(yōu)策略，它滿足：相對前面決策所形成的狀態(tài)而言，余下的子策略必然構(gòu)成“最優(yōu)子策略”。無后效性原則給定某一階段的狀態(tài)，則在這一階段以后過程的發(fā)展不受這階段以前各段狀態(tài)的影響，所有各階段都確定時，整個過程也就確定了。這個性質(zhì)意味著過程的歷史只能通過當(dāng)前的狀態(tài)去影響它的未來的發(fā)展，這個性質(zhì)稱為無后效性。機器分配

3、w 總公司擁有高效生產(chǎn)設(shè)備M臺，準備分給下屬的N個公司。各分公司若獲得這些設(shè)備，可以為國家提供一定的盈利。問：如何分配這M臺設(shè)備才能使國家得到的盈利最大？求出最大盈利值。其中M=15，N=10。分配原則：每個公司有權(quán)獲得任意數(shù)目的設(shè)備，但總臺數(shù)不得超過總設(shè)備數(shù)M。w 數(shù)據(jù)文件格式為：第一行保存兩個數(shù)，第一個數(shù)是設(shè)備臺數(shù)M，第二個數(shù)是分公司數(shù)N。接下來是一個M*N的矩陣，表明了第I個公司分配J臺機器的盈利。 分析w 用機器數(shù)來做狀態(tài)，數(shù)組FI，J表示前I個公司分配J臺機器的最大盈利。則狀態(tài)轉(zhuǎn)移方程為:w FI，J=MaxFI-1，K + ValueI，J-K (1=I=N,1=J=M,0=K=J

4、 )w 初始值: F(0,0)=0w 時間復(fù)雜度O(N*M2)最長不下降序列 w 設(shè)有整數(shù)序列b1,b2,b3,bm，若存在下標(biāo)i1i2i3 in，且bi1bi2bi3 bin，則稱 b1,b2,b3,bm中有長度為n的不下降序列bi1 , bi2 ,bi3 ,bin 。w 求序列b1,b2,b3,bm中所有長度(n)最大不下降子序列w 輸入：整數(shù)序列。w 輸出：最大長度n和所有長度為n的序列個數(shù)。分析（1）設(shè)f(i)為前i個數(shù)中的最大不下降序列長度 , 則w f(i)=maxf(j)+1 (1=ji=m, bjbi)w 邊界為F(1)=1(2)設(shè)t(i)為前i個數(shù)中最長不下降序列的個數(shù),則w

5、 t(i)=t(j) (1=ji=m , bjbi, f(i)=f(j)-1) w 初始為t(i)=1w 當(dāng)f(i)=n時，將t(i)累加w 舉例： 1 2 3 4 6 5 8 10 9 f: 1 2 3 4 5 5 6 7 7 t: 1 1 1 1 1 1 2 2 2答案：f=7時，邊界為t=4進一步(3)求本質(zhì)不同的最長不下降序列個數(shù)有多少個？ 如：1 2 3 4 6 5 8 10 9 有， 1 2 3 4 6 8 10 , 1 2 3 4 5 8 10, 1 2 3 4 6 8 9 ,1 2 3 4 5 8 9 都是本質(zhì)不同的。 但對于 1 2 2 3 3 5 4 f 1 2 2 3 3

6、 5 4 t 1 1 1 2 2 4 4 答案有8個，其中4個1 2 3 5 ，4個1 2 3 4改進算法w 上例顯然對于相兩個相同的數(shù)，重復(fù)算了多次因此，我們對算法進行改進：w 對原序列按b從小到大（當(dāng)bi=bj時按F從大到?。┡判?，增設(shè)Order(i)記錄新序列中的i個數(shù)在原序列中的位置。可見，w 求t(i)時，當(dāng)f(j)=f(j+1),b(j)=b(j+1)且Order(j+1)Order(i)時，便不累加t(j)。這樣就避免了重復(fù)。w 上述算法的時間復(fù)雜度為O(n2) 凸多邊形三角劃分 w 給定一個具有N（N50）個頂點（從1到N編號）的凸多邊形，每個頂點的權(quán)均已知。問如何把這個凸多邊

7、形劃分成N-2個互不相交的三角形，使得這些三角形頂點的權(quán)的乘積之和最小？w 輸入文件：第一行 頂點數(shù)Nw 第二行 N個頂點（從1到N）的權(quán)值w 輸出格式：最小的和的值w 各三角形組成的方式w 輸入示例：5w 122 123 245 231 w 輸出示例：The minimum is ：12214884w The formation of 3 triangle:w 3 4 5, 1 5 3, 1 2 3 分析w 設(shè)FI,J（IJ）表示從頂點I到頂點J的凸多邊形三角剖分后所得到的最大乘積，我們可以得到下面的動態(tài)轉(zhuǎn)移方程：w FI,J=MinFI,K+FK,J+SI*SJ*SK (0IKJ=N)w

8、初始條件:F1，2=0w 目標(biāo)狀態(tài):F1,Nw 但我們可以發(fā)現(xiàn),由于這里為乘積之和，在輸入數(shù)據(jù)較大時有可能超過長整形范圍，所以還需用高精度計算 系統(tǒng)可靠性 w 一個系統(tǒng)由若干部件串聯(lián)而成，只要有一個部件故障，系統(tǒng)就不能正常運行，為提高系統(tǒng)的可靠性，每一部件都裝有備用件，一旦原部件故障，備用件就自動進入系統(tǒng)。顯然備用件越多，系統(tǒng)可靠性越高，但費用也越大，那么在一定總費用限制下，系統(tǒng)的最高可靠性等于多少？w 給定一些系統(tǒng)備用件的單價Ck，以及當(dāng)用Mk個此備用件時部件的正常工作概率Pk（Mk），總費用上限C。求系統(tǒng)可能的最高可靠性。 w 輸入文件格式：第一行：n C第二行：C1 P1(0) P1(1

9、) P1(X1) （0=X1=C/Ck） 第 n 行：Cn Pn(0) Pn(1) Pn(Xn) （0=Xn=C/Cn）分析w 例：輸入：2 20 3 0 .6 0.65 0.7 0.75 0.8 0.85 0.9 5 0.7 0.75 0.8 0.8 0.9 0.95 輸出：0.6375w 設(shè)FI,money表示將money的資金用到前I項備用件中去的最大可靠性，則有w FI,money = maxFI-1 ,moneyk*CostI *PI,k w (0=I=n,0=K= money div Cost(I) )w 初始： F0,0=0w 目標(biāo)： Fn,C快餐問題 w Peter最近在R市開

10、了一家快餐店，為了招攬顧客，該快餐店準備推出一種套餐，該套餐由A個漢堡，B個薯條和C個飲料組成。價格便宜。為了提高產(chǎn)量，Peter從著名的麥當(dāng)勞公司引進了N條生產(chǎn)線。所有的生產(chǎn)線都可以生產(chǎn)漢堡，薯條和飲料，由于每條生產(chǎn)線每天所能提供的生產(chǎn)時間是有限的、不同的，而漢堡，薯條和飲料的單位生產(chǎn)時間又不同。這使得Peter很為難，不知道如何安排生產(chǎn)才能使一天中生產(chǎn)的套餐產(chǎn)量最大。請你編一程序，計算一天中套餐的最大生產(chǎn)量。為簡單起見，假設(shè)漢堡、薯條和飲料的日產(chǎn)量不超過100個。w 輸入:第一行為三個不超過100的正整數(shù)A、B、C中間以一個空格分開。第二行為3個不超過100的正整數(shù)p1,p2,p3分別為漢

11、堡，薯條和飲料的單位生產(chǎn)耗時。中間以一個空格分開。第三行為N(0=0=10)，第四行為N個不超過10000的正整數(shù)，分別為各條生產(chǎn)流水線每天提供的生產(chǎn)時間，中間以一個空格分開。w 輸出:每天套餐的最大產(chǎn)量。 分析w 本題是一個非常典型的資源分配問題。由于每條生產(chǎn)線的生產(chǎn)是相互獨立，不互相影響的，所以此題可以以生產(chǎn)線為階段用動態(tài)規(guī)劃求解。w 狀態(tài)表示：用pi,j,k表示前i條生產(chǎn)線生產(chǎn)j個漢堡，k個薯條的情況下最多可生產(chǎn)飲料的個數(shù)。w 用ri,j,k表示第i條生產(chǎn)線生產(chǎn)j個漢堡，k個薯條的情況下最多可生產(chǎn)飲料的個數(shù)。w 態(tài)轉(zhuǎn)移方程 ： pi,j,k = Maxpi-1,j1,k1+ri,j-j1

12、,k-k1 ( 0=j1=j=100,0=k1=k=100, 且(j-j1)*p1+(k-k1)*p2=Ti-第i條生產(chǎn)線的生產(chǎn)時間 )w ri,j-j1,k-k1=(Ti-(j-j1)*p1+(k-k1)*p2) div p3 ;w 此算法的時間復(fù)雜度為O(N*1004), 優(yōu)化w 在本題中，可以在動態(tài)規(guī)劃方法中加入了貪心算法思想：即首先計算出每天生產(chǎn)套數(shù)的上限值（由A,B,C計算，即min100 div A，100 div B，100 div c），接著，用貪心法計算出這N條流水線可以生產(chǎn)的套數(shù)，并與上限比較，大于則輸出上限值并退出，否則再調(diào)用動態(tài)規(guī)劃；同時，在運行動態(tài)規(guī)劃的過程中，也可以

13、每完成一階段工作便與上限值進行比較，這樣以來，便可望在動態(tài)規(guī)劃完成前提前結(jié)束程序。其算法設(shè)計為：w S1：讀入數(shù)據(jù)。w S2：貪心求上限并計算出一可行解，判斷是否需進行下一步。w S3：動態(tài)規(guī)劃求解。w S4：輸出。其他優(yōu)化方法w 1.存儲結(jié)構(gòu)：由于每一階段狀態(tài)只與上一階段狀態(tài)有關(guān)，所以我們可以只用兩個100*100的數(shù)組滾動實現(xiàn)。但考慮到滾動是有大量的賦值，可以改進為動態(tài)數(shù)組，每次交換時只需交換指針即可，這樣比原來數(shù)組間賦值要快。w 2.減少循環(huán)次數(shù)：在計算每一階段狀態(tài)過程中無疑要用到4重循環(huán)，我們可以這樣修改每一重循環(huán)的起始值和終數(shù)，其中q1,q2為A，B上限值。w 原起始值 改進后的起始

14、值wfor i:=1 to n do for i:=1 to n do wfor j:=0 to toti div p1 do for j:=0 to min(q1,toti div p1) dowfor k:=0 to (toti-p1*j) div p2 do for k:=0 to min(q2,(toti-p1*j)div p2) dowfor j1:=0 to j do for j1 := max(0,j-ti div p1) to min(j,toti-1 div p1) dow for k1 := 0 to k do for k1:=max(0,k-(ti-(j-j1)*p1)

15、div p2) to min(k,(toti-1-p1*j1)div p2) do 石子合并 w 在一園形操場四周擺放N堆石子(N100),現(xiàn)要將石子有次序地合并成一堆.規(guī)定每次只能選相臨的兩堆合并成一堆,并將新的一堆的石子數(shù),記為該次合并的得分。編一程序,由文件讀入堆數(shù)N及每堆石子數(shù)(20),(1)選擇一種合并石子的方案,使得做N-1次合并,得分的總和最少 (2) 選擇一種合并石子的方案,使得做N-1次合并,得分的總和最大w 輸入數(shù)據(jù): 第一行為石子堆數(shù)N; 第二行為每堆石子數(shù),每兩個數(shù)之間用一空格分隔.w 輸出數(shù)據(jù) :從第1至第N行為得分最小的合并方案. 第N+1行為空行.從N+2到2N+

16、1行是得分最大的合并方案. 示例貪心法 N=5 石子數(shù)分別為3 4 6 5 4 2。用貪心法的合并過程如下：第一次 3 4 6 5 4 2得分 5第二次 5 4 6 5 4得分9第三次 9 6 5 4得分9第四次 9 6 9得分15第五次 15 9得分24第六次24總分：62然而仔細琢磨后，發(fā)現(xiàn)更好的方案：第一次3 4 6 5 4 2得分 7第二次7 6 5 4 2得分13第三次13 5 4 2得分6第四次13 5 6得分11第五次 13 11得分24第六次24總分：61顯然，貪心法是錯誤的。 動態(tài)規(guī)劃 w 用datai,j表示將從第i顆石子開始的接下來j顆石子合并所得的分值，w maxi,j

17、表示將從第i顆石子開始的接下來j顆石子合并可能的最大值，那么：w maxi,j = max(maxi, k + maxi + k, j k + datai,k + datai+k, jk) (2=k=j)w maxi,1 = 0w 同樣的，我們用mini,j表示將第從第i顆石子開始的接下來j顆石子合并所得的最小值，可以得到類似的方程：w mini,j = min(mini, k + mini + k, j k + datai,k + datai+k, j k) (0=k=j)w mini,0 = 0w 這樣，我們完美地解決了這道題。時間復(fù)雜度也是O(n2)。積木游戲 w 一種積木游戲，游戲者有

18、N塊編號依次為1，2，N的長方體積木。第I塊積木通過同一頂點三條邊的長度分別為ai,bi,ci（i=1,2,N），1 從N塊積木中選出若干塊，并將他們摞成M（1= M = N）根柱子，編號依次為1,2,M，要求第k根柱子的任意一塊積木的編號都必須大于第K-1根柱子任意一塊積木的編號（2=K=n），x,y是上面一塊積木接觸面的兩條邊（x=y），則一定滿足m.=x和n=y；w 下面的積木的編號要小于上面的積木的編號。w 請你編一程序，尋找一種游戲方案，使得所有能摞成的M根柱子的高度之和最大。積木游戲w 輸入數(shù)據(jù)：w 文件的第一行是兩個正整數(shù)N和M（1= M = N =100）,分別表示積木總數(shù)和要

19、求摞成的柱子數(shù)。這兩個數(shù)之間用一個空格符隔開。接下來的N行是編號從1到N個積木的尺寸，每行有三個1至500之間的整數(shù)，分別表示該積木三條邊的長度。同一行相鄰兩個數(shù)之間用一個空格符隔開。w 輸出數(shù)據(jù)：w 文件只有一行，是一個整數(shù)，表示所求得的游戲方案中M根柱子的高度之和 分析w 設(shè)（1） fi,j,k表示以第i塊積木的第k面為第j根柱子的頂面的最優(yōu)方案的高度總和； （2）blocki,k 記錄每個積木的三條邊信息（blocki,4:=blocki,1; blocki,5:=blocki,2）。其中blocki,j+2表示當(dāng)把第i塊積木的第j面朝上時所對應(yīng)的高，即所增加的高度；（3）cani,k,

20、p,kc表示第I塊積木以其第k面朝上，第p塊積木以第kc面朝上時，能否將積木I放在積木p的上面。1表示能，0表示不能。對于fi,j,k, 有兩種可能： 1. 除去第I塊積木，第j根柱子的最上面的積木為編號為p的，若第p塊積木以第kc面朝上，必須保證當(dāng)?shù)贗塊積木以k面朝上時能夠被放在上面，即cani,k,p,kc=1； 2. 第i塊積木是第j根柱子的第一塊積木，第j-1根柱子的最上面為第p塊積木，則此時第p塊積木可以以任意一面朝上。則有：動態(tài)規(guī)劃)31, 11 (2, 1,max) 1, 31 , 11 (2,maxmax,kcipjiblockkcjpfkcpkicankcipjiblockk

21、cjpfkjif且w 邊界條件：w f1,1,1:=block1,1,3; f1,1,2:=block1,1,4; f1,1,3:=block1,1,5;w fi,0,k:=0; (1= i = n, 1= k = 3);w 時間復(fù)雜度為O(n2*m) 免費餡餅 w SERKOI最新推出了一種叫做“免費餡餅”的游戲。w 游戲在一個舞臺上進行。舞臺的寬度為W格，天幕的高度為H格，游戲者占一格。開始時，游戲者站在舞臺的正中央正中央，手里拿著一個托盤。w 游戲開始后，從舞臺天幕頂端的格子中不斷出現(xiàn)餡餅并垂直下落。游戲者左右移動去接餡餅。游戲者每秒可以向左或右移動一格或兩格，也可以站在愿地不動。w 餡

22、餅有很多種，游戲者事先根據(jù)自己的口味，對各種餡餅依次打了分。同時在8-308電腦的遙控下，各種餡餅下落的速度也是不一樣的，下落速度以格/秒為單位。當(dāng)餡餅在某一秒末恰好恰好到達游戲者所在的格子中，游戲者就收集到了這塊餡餅。w 寫一個程序，幫助我們的游戲者收集餡餅，使得收集的餡餅的分數(shù)之和最大。免費餡餅w 輸入數(shù)據(jù)：輸入文件的第一行是用空格分開的兩個正整數(shù)，分別給出了舞臺的寬度W（199之間的奇數(shù)）和高度H（1 100之間的整數(shù)）。w 接下來依餡餅的初始下落時間順序給出了一塊餡餅信息。由四個正整數(shù)組成，分別表示了餡餅的初始下落時刻（0 1000秒），水平位置、下落速度（1 100）以及分值。游戲開

23、始時刻為0。從1開始自左向右依次對水平方向的每格編號。w 輸出數(shù)據(jù)：輸出文件的第一行給出了一個正整數(shù)，表示你的程序所收集到的最大分數(shù)之和。分析w 我們將問題中的餡餅信息用一個表格存儲。表格的第I行第J列表示的是游戲者在第I秒到達第J列所能取得的分值。那么問題便變成了一個類似數(shù)字三角形的問題：從表格的第一行開始往下走，每次只能向左或右移動一格或兩格，或不移動走到下一行。怎樣走才能得到最大的分值。w 因此，我們很容易想到用動態(tài)規(guī)劃求解。w FI,J表示游戲進行到第表示游戲進行到第I秒，這時游戲者站在第秒，這時游戲者站在第J列時列時所能得到的最大分值。那么動態(tài)轉(zhuǎn)移方程為：所能得到的最大分值。那么動態(tài)

24、轉(zhuǎn)移方程為： FI,J = Max FI-1,K + 餡餅的分值餡餅的分值 ( J-2=K=J+2 )商店購物 某商店中每種商品都有一個價格。例如，一朵花的價格是2 ICU(ICU 是信息學(xué)競賽的貨幣的單位）;一個花瓶的價格是5 ICU。為了吸引更多的顧客，商店提供了特殊優(yōu)惠價。 特殊優(yōu)惠商品是把一種或幾種商品分成一組。并降價銷售。例如:3朵花的價格不是6而是5 ICU ;2個花瓶加1朵花是10 ICU不是12 ICU。 編一個程序，計算某個顧客所購商品應(yīng)付的費用。要充分利用優(yōu)惠價以使顧客付款最小。請注意，你不能變更顧客所購商品的種類及數(shù)量，即使增加某些商品會使付款總數(shù)減小也不允許你作出任何變

25、更。假定各種商品價格用優(yōu)惠價如上所述，并且某顧客購買物品為:3朵花和2個花瓶。那么顧客應(yīng)付款為14 ICU因為: 1朵花加2個花瓶: 優(yōu)惠價:10 ICU 2朵花 正常價: 4 ICU商店購物輸入數(shù)據(jù) 第一個文件INPUTTXT的格式為:第一行是一個數(shù)字B（0B5），表示所購商品種類數(shù)。下面共B行，每行中含3個數(shù)C，K，P。C 代表商品的編碼（每種商品有一個唯一的編碼），1C999。K代表該種商品購買總數(shù)，1K5。P 是該種商品的正常單價（每件商品的價格），1P999。請注意，購物筐中最多可放5*525件商品。第二個文件OFFERTXT的格式為:第一行是一個數(shù)字S（0S99），表示共有S種優(yōu)惠

26、。下面共S行，每一行描述一種優(yōu)惠商品的組合中商品的種類。下面接著是幾個數(shù)字對（C，K），其中C代表商品編碼，1C9 99。K代表該種商品在此組合中的數(shù)量，1K5。本行最后一個數(shù)字P（1 P9999）代表此商品組合的優(yōu)惠價。當(dāng)然， 優(yōu)惠價要低于該組合中商品正常價之總和。輸出數(shù)據(jù) 在輸出文件OUTPUTTXT中寫 一個數(shù)字（占一行）， 該數(shù)字表示顧客所購商品（輸入文件指明所購商品）應(yīng)付的最低貨款。 分析w 由于動態(tài)規(guī)劃要滿足無后效性和最優(yōu)化原理，所以我們來分析此題是否滿足以上兩點。首先確定狀態(tài)，商品不超過5種，而每種采購的數(shù)量又不超過5，那么用一個五元組來表示第i種商品買Ai的最小費用。w F F

27、（A A1 1，A A2 2，A A3 3，A A4 4，A A5 5） （1 1）w 考慮這個狀態(tài)的由來，當(dāng)然，我們不用優(yōu)惠商品也可以買，顯然這樣不是最優(yōu)。于是如果我們能夠使用第i條商品組合的話，狀態(tài)就b變?yōu)榱耍簑 F F（A A1 1-S-SI1I1，A A2 2-S-SI2I2，A A3 3-S-SI3I3，A A4 4-S-SI4I4，A A5 5-S-SI5I5） （2 2）w 這樣的話，狀態(tài)1的費用為狀態(tài)2的費用加上Si的費用，而狀態(tài)2的費用必須最低（很顯然，用反證法即可），同時，我們也不管狀態(tài)2是如何來的（因為每一個優(yōu)惠商品組合的使用是沒有限制的），所以本題既滿足無后效性，又符合

28、最優(yōu)化原理，同時還有大量重疊子問題產(chǎn)生，動態(tài)規(guī)劃解決此題是最好不過了。狀態(tài)轉(zhuǎn)移方程w F a, b, c, d, e = MinFa-Si1,b-Si2,c-Si3,d-Si4,e-Si5+SaleCostSi (0=i=S, 0=a, b, c, d, e=5)初始條件為： F a, b, c, d, e = Cost1*a+Cost2*b+Cost3*c+Cost4*d+Cost5*e添括號問題 w 有一個由數(shù)字1，2，. ，9組成的數(shù)字串（長度不超過200），問如何將M(M=20)個加號(+)插入到這個數(shù)字串中，使所形成的算術(shù)表達式的值最小。請編一個程序解決這個問題。w 注意：w 加號不

29、能加在數(shù)字串的最前面或最末尾，也不應(yīng)有兩個或兩個以上的加號相鄰。w M保證小于數(shù)字串的長度。w 例如：數(shù)字串79846，若需要加入兩個加號，則最佳方案為79+8+46，算術(shù)表達式的值133。w 輸入格式w 從鍵盤讀入輸入文件名。數(shù)字串在輸入文件的第一行行首（數(shù)字串中間無空格且不折行），的值在輸入文件的第二行行首。w 輸出格式w 在屏幕上輸出所求得的最小和的精確值。分析w 考慮到數(shù)據(jù)的規(guī)模超過了長整型,我們注意在解題過程中采用高精度算法.w 規(guī)劃方程:w FI,J = MIN FI-1,K + NUMK+1,J (I-1=K=J-1)w 邊界值:F0,I := NUM1,I ;w FI，J表示前

30、J個數(shù)字中添上I個加號后得到的最小值。w NUMI，J表示數(shù)字串第I位到第J位的數(shù)w 上述問題的每一步，都只與上一步有關(guān)。因此可以采用滾動數(shù)組w 程序的時間效率約為 20 * 200 * 200 最長前綴 w 一些生物體的復(fù)雜結(jié)構(gòu)可以用其基元的序列表示，而一個基元用一個大寫英文字符串表示。生物學(xué)家的一個問題就是一個這樣的長序列分解為基元（字符串）的序列。對于給定的基元集合P，如果可以從中選出N個基元P1，P2，P3，.,Pn，將它們各自對應(yīng)的字符串依次連接后得到一個字符串S，稱S可以由基元集合P構(gòu)成。在從P中挑選基元時，一個基元可以使用多次，也可不用。例如，序列 ABABACABAAB 可以由

31、基元集合A，AB，BA，CA，BBC 構(gòu)成。w 字符串的前K個字符為該字符串的前綴，其長度為K。請寫一個程序，對于輸入的基元集合P和字符串T，求出一個可以由基元集合P構(gòu)成的字符串T的前綴，要求該前綴的長度盡可能長，輸出其長度。最長前綴w 輸入數(shù)據(jù)：有兩個輸入文件 INPUT.TXT，DATA.TXTINPUT.TXT 的第一行是基元集合P中的基元數(shù)目N（1=N=100）,隨后有2N行，每兩行描述一個基元，第一行為該基元的長度L（1=L=20）。隨后一行是一個長度為L的大寫英文字符串，表示該基元。每個基元互不相同。DATA.TXT 描述要處理的字符串T，每一行行首有一個大寫字母，最后一行是一個字

32、符.,表示字符串結(jié)束。T的長度最小為1，最大不超過500000。w 輸出數(shù)據(jù)：OUTPUT.TXT。只有一行，一個數(shù)字，表示可以由P構(gòu)成的T的最長前綴的長度。分析w 本題可以簡述為: 從一個集合里選出若干個基元,使其組成字符串T的前綴,求最長前綴的長度. w 對于T的每個字符，其狀態(tài)可分為兩種：w 在此之前的所有字符（包括本身）可匹配(true)、不可匹配(false)。(可匹配是指可以由集合里的基元組成)w 用Fi表示第i個字符的狀態(tài)，finda,b表示由第a至b位的字符組成的子串是否存在于集合中，則，F(xiàn)i = Fi or (Fk and findk+1,j) (0=k=i-1)w 初始條件

33、: if i=0 then Fi:= true else Fi:= false分析w 由于T的長度最大達500000，無法存放所有狀態(tài)，但集合里基元長度不超過20，因此可只保留當(dāng)前20位字符與狀態(tài)。當(dāng)20位字符都不可以匹配時，停止運算，最后一個狀態(tài)為true的字符的位置，即為所求。w 為了便于操作，可用字符串表示狀態(tài)，0表false、1表true.w 為了便于查找，可將基元按長度存儲。w 形如：si,j，表示長度為 i的第 j個基元。w 亦可采用樹的結(jié)構(gòu)存儲基元，構(gòu)造一種多叉樹（最多26叉），查找時順著相應(yīng)字母，定位到相應(yīng)分支。這樣速度要快些，但程序更復(fù)雜。大家可以比較一下。w 按樹結(jié)構(gòu)算，時

34、間復(fù)雜度為O(500000*L*L),勉強可以承受。多邊形 w 多角形是一個單人玩的游戲，開始時有一個N個頂點的多邊形。如圖，這里N N=4。每個頂點有一個整數(shù)標(biāo)記，每條邊上有一個“+”號或“*”號。邊從1編號到N。 第一步，一條邊被拿走；隨后各步包括如下：w 選擇一條邊E和連接著E的兩個頂點V V1和 V V2；w 得到一個新的頂點，標(biāo)記為V1與V2通過邊E E上的運算符運算的結(jié)果。w 最后，游戲中沒有邊，游戲的得分為僅剩余的一個頂點的值。 -7425+*1234+*樣例 -7 4 2 5 + * 1 2 4 + 42+*24-24+2-40寫一個程序，對于給定一個多邊形，計算出可能的最高得

35、分，并且列出得到這個分數(shù)的過程。分析 分析w 我們在這條“線”當(dāng)中繼續(xù)刪邊，并且每次刪邊都使被刪邊兩旁的點按邊上的操作符合并，圖五。這樣進行了n-1次刪邊操作后，“線”變成了一個點。我們的目的，就是安排刪邊的順序，使最后的點上的數(shù)盡可能的大。w 拿到題目之后，我們馬上可以想到用枚舉法枚舉刪邊的先后順序。但邊數(shù)最大可以達到50，枚舉的復(fù)雜將會有50！。因此枚舉算法馬上被排除了。 w 對最優(yōu)化問題的求解，我們往往可以使用動態(tài)規(guī)劃來解決。這道題是不是可以使用動態(tài)規(guī)劃呢？w 我們先對題目進行一些變化原題中頂點上的數(shù)可以為負數(shù)，現(xiàn)在我們規(guī)定這個數(shù)一定大于等于0；原題中邊可以為乘號，現(xiàn)在我們規(guī)定只能為加號

36、。w 題意改變后，我們想到了什么？對！“石子合并”。動態(tài)規(guī)劃w 我們先枚舉第一次刪掉的邊，然后再對每種狀態(tài)進行動態(tài)規(guī)劃求最大值 w 用f(I,j)表示從j開始，進行i次刪邊操作所能得到的最大值，num(i)表示第i個頂點上的數(shù)，那么：)(), 1 (),(),(max),(11inumifkikjfikfjifik進一步分析w 現(xiàn)在我們來考慮加入乘號后的情況。w 由于所有的頂點上的數(shù)都為非負數(shù)，因此即使有了乘法，函數(shù)f的無后效性并不被破壞。我們可以在前一方程的基礎(chǔ)上進行改進：（opr(i)表示第i條邊上的操作符） )(), 1 (),(max),(11inumifkikjikactjifiky

37、2)f(x2,*y1)f(x1, - 1)-opr(x2y2)f(x2,y1)f(x1, 1)-opr(x2)2, 2, 1, 1(時，當(dāng)時，當(dāng)yxyxAct進一步分析w 最后，我們允許頂點上出現(xiàn)負數(shù)。以前的方程還適不適用呢？w 這個例子的最優(yōu)解應(yīng)該是（3+2）*（-9）*（-5）=250，然而如果沿用以前的方程，得出的解將是（-10）*3+2）*（-5）=140。為什么？w 我們發(fā)現(xiàn)，兩個負數(shù)的積為正數(shù)；這兩個負數(shù)越小，它們的積越大。我們從前的方程，只是盡量使得局部解最大，而從來沒有想過負數(shù)的積為正數(shù)這個問題。 -932-5*圖六+最終？w 我們引入函數(shù)fmin和fmax來解決這個問題。fm

38、ax(I,j) 表示從j開始，進行i次刪邊操作所能得到的最大值，fmin(I,j) 表示從j開始，進行i次刪邊操作所能得到的最小值 。)(), 1 (),min(min),min(),max(max),max(1111inumifkikjikactjifkikjikactjifikik函數(shù)actmax與actmin的構(gòu)造是十分關(guān)鍵的。首先討論actmax(x1,y1,x2,y2)的構(gòu)造：當(dāng)opr(x2-1)=+時，actmax=fmax(x1,y1)+fmax(x2,y2)當(dāng)opr(x2-1)=*時， actmax=max(fmax(x1,y1)*fmax(x2,y2),fmin(x1,y1)

39、*fmin(x2,y2) 完美解決w 接下來討論actmin(x1,y1,x2,y2)的構(gòu)造：w 當(dāng)opr(x2-1)=+時，actmin=fmin(x1,y1)+fmin(x2,y2)w opr(x2-1)=*時， actmin=min(fmax(x1,y1)*fmin(x2,y2),fmin(x1,y1)*fmax(x2,y2)w 到此為止，整個問題圓滿解決了。算法的空間復(fù)雜度為n2，算法時間復(fù)雜度為n4（先要枚舉每一條邊，然后再用復(fù)雜度為n3的動態(tài)規(guī)劃解決）。選課 w 大學(xué)里實行學(xué)分。每門課程都有一定的學(xué)分，學(xué)生只要選修了這門課并考核通過就能獲得相應(yīng)的學(xué)分。學(xué)生最后的學(xué)分是他選修的各門課

40、的學(xué)分的總和。w 每個學(xué)生都要選擇規(guī)定數(shù)量的課程。其中有些課程可以直接選修，有些課程需要一定的基礎(chǔ)知識，必須在選了其它的一些課程的基礎(chǔ)上才能選修。例如，數(shù)據(jù)結(jié)構(gòu)必須在選修了高級語言程序設(shè)計之后才能選修。我們稱高級語言程序設(shè)計是數(shù)據(jù)結(jié)構(gòu)的先修課。每門課的直接先修課最多只有一門。兩門課也可能存在相同的先修課。為便于表述每門課都有一個課號，課號依次為1，2，3，。 選課w 下面舉例說明w 上例中1是2的先修課，即如果要選修2，則1必定已被選過。同樣，如果要選修3，那么1和2都一定已被選修過。w 學(xué)生不可能學(xué)完大學(xué)所開設(shè)的所有課程，因此必須在入學(xué)時選定自己要學(xué)的課程。每個學(xué)生可選課程的總數(shù)是給定的?，F(xiàn)

41、在請你找出一種選課方案，使得你能得到學(xué)分最多，并且必須滿足先修課優(yōu)先的原則。假定課程之間不存在時間上的沖突。選課w 輸入輸入 輸入文件的第一行包括兩個正整數(shù)M、N（中間用一個空格隔開）其中M表示待選課程總數(shù)（1M1000)，N表示學(xué)生可以選的課程總數(shù)（1NM)。 以下M行每行代表一門課，課號依次為1，2M。每行有兩個數(shù)（用一個空格隔開），第一個數(shù)為這門課的先修課的課號（若不存在先修課則該項為0），第二個數(shù)為這門課的學(xué)分。學(xué)分是不超過10的正整數(shù)。w 輸出輸出 輸出文件第一行只有一個數(shù)，即實際所選課程的學(xué)分總數(shù)。以下N行每行有一個數(shù)，表示學(xué)生所選課程的課號。樣例分析7 42 20 10 42 1

42、7 17 62 2表12157346圖202157346圖1分析w 們可以選取某一個點k的條件只是它的父節(jié)點已經(jīng)被選取或者它自己為根節(jié)點；而且我們不論如(何取k的子孫節(jié)點，都不會影響到它父節(jié)點的選取情況，這滿足無后效性原則。于是我們猜測，是不是可以以節(jié)點為階段，進行動態(tài)規(guī)劃呢？w 我們用函數(shù)f(I,j)表示以第i個節(jié)點為父節(jié)點，取j個子節(jié)點的最佳代價，則：w 可是如此規(guī)劃，其效率與搜索毫無差別，雖然我們可以再次用動態(tài)規(guī)劃來使它的復(fù)雜度變?yōu)槠椒郊墸@得過于麻煩。 jnchnchjnchnchnchjnchnichnchnchjchinchinchifnchchfnchchfjif1111221

43、13) 1(21),()2, 2()1, 1(max),(改造樹w 轉(zhuǎn)變?yōu)槎鏄?。如果兩?jié)點a,b同為兄弟，則將b設(shè)為a的右節(jié)點；如果節(jié)點b是節(jié)點a的兒子，則將節(jié)點b設(shè)為節(jié)點a的左節(jié)點。樹改造完成后如圖3。w 我們用函數(shù)f(I,j)表示以第i個節(jié)點為父節(jié)點，取j個子節(jié)點的最佳代價，這和前一個函數(shù)表示的意義是一致的，但方程有了很大的改變：023014765圖3動態(tài)規(guī)劃w 1=i=m,1=j=n,0=kj w 這個方程的時間復(fù)雜度最大為n3，十分優(yōu)秀了。w 在具體實現(xiàn)這道題時，我們可以自頂而下，用遞歸進行樹的遍歷求解 max),()1,(),(),(iskjrightcfkleftcfjright

44、cfjifHPC (Winter Camp 2001) 描述抽象為：描述抽象為：A類任務(wù)：A1，A2，AmB類任務(wù)：B1，B2，BnP個接點：1，2，P在節(jié)點i連續(xù)處理x個A、B類任務(wù)的時間 Kia x2、 Kib x2節(jié)點i轉(zhuǎn)入工作狀態(tài)A、B類任務(wù)的啟動時間 Tia， Tib輸入：輸入：1=Na ， Nb=60，1=P=20 1=Tia， Tib =1000， 1=Kia， Kib 1p 1 P1的情況：w 第一個節(jié)點負責(zé)了i個任務(wù)A和j個任務(wù)B，則w 剩下的a i個任務(wù)A和b j個任務(wù)B都必須由后p 1個節(jié)點完成。w 設(shè)f(p, a, b)表示在后p個節(jié)點上處理a個A類任務(wù)，b個B類任務(wù)所

45、需的最少時間。有： f(p, a, b) = min(0ia, 0jb)maxg(i, j), f(p 1, a i, b j) 總結(jié)：w 由于計算f(p)時，只需用到f(p 1)的結(jié)果，故可以使用滾動數(shù)組。這樣，計算過程中，只需保存ga, gb, g, f(p 1), f(p)這5個大小為n2的數(shù)組，故空間復(fù)雜度是O(n2)。w 計算數(shù)組g的復(fù)雜度為O(n3)，一共有p個節(jié)點，故時間復(fù)雜度是O(pn3)。計算數(shù)組f的復(fù)雜度為O(pn4)。所以，總的時間復(fù)雜度為O(pn4)。w 在這個例子中，我們用f來表示目標(biāo)問題。在求f之前，先要求出g，而在求g的時候，也采用了動態(tài)規(guī)劃。我們稱之為多次動態(tài)規(guī)

46、劃。很多題目中，動態(tài)規(guī)劃并不是單一出現(xiàn)的，但有些例子中，這種多層次的結(jié)構(gòu)并不明顯，下一個例子將討論這個問題。交叉匹配交叉匹配 描述：兩行正整數(shù)。第一行中有一個數(shù)和第二行中的一個數(shù)都為r，將這兩個數(shù)用線段連起來。稱這條線段為r匹配線段。例如下圖就顯示了一條3匹配線段和一條2匹配線段。34622137對于給定的輸入，找到畫出最多的匹配線段的方式，使得：1）每條a匹配線段恰好和一條b匹配線段相交，且ab，a, b指代任何值，并非特定值。2）不存在兩條線段都從一個數(shù)出發(fā)。計算出匹配線段的最多個數(shù)。分析：w an：存儲第一行的數(shù) bm：存儲第二行的數(shù)w 設(shè) f(i, j)：表示如下圖所示的兩行數(shù)據(jù)，可以

47、畫出的最多的匹配線段數(shù)。 a1a2Aib1b2Bj沒有從ai出發(fā)的匹配線段 解為f(i-1,j)a1a2Aib1b2Bja1a2Aib1b2Bj2. 沒有從bj出發(fā)的匹配線段 解為f(i,j-1) 3.ai和bj處，各引出一條匹配線段，這時必須aibj。設(shè)ai = bv，bj = au。從ai向bv，bj向au各引一條匹配線段，這兩條線段必然相交。這種情況的解即為f(u 1, v 1) + 2。 a1a2Au-1b1b2Bu-1Au AiBu Bjiuuajbjvvbiajbiavufjifjifjif112)1, 1()1,(), 1(max),(且且其中該算法的復(fù)雜度：O(nm)2)。優(yōu)化

48、 ？w 從什么地方入手呢？w 是否要改變思路？w 有更好的狀態(tài)轉(zhuǎn)移方程嗎？從問題的特性入手！如果存在au = bj，且u u i，則用bj向au的匹配線段，代替bj向au的匹配線段，所得到的解不會變差。因此，u的選擇是越靠后越好。同理，v的選擇也是越靠后越好。,2) 1, 1() 1,(), 1(max),(uajbiuuuuajbvbiajvvvvbiajbiavufjifjifjif使得且不存在使得且不存在其中a1a2Aub1b2BvAuAiBj對于確定的i和j，相應(yīng)的u和v的值也是確定的，這些值可以預(yù)先求出。而求法也是利用動態(tài)規(guī)劃。設(shè)相應(yīng)u和v的值分別為ui, j和vi, j。 11 1) 1,(),( 11 1), 1(),(iajbjiajbjivjivjbiaijbiajiujiu這樣，原動態(tài)轉(zhuǎn)移方程可變?yōu)椋?2) 1),(, 1),() 1,(), 1(max),(jbiajivjiufjifjifjif該算法需要保存f，u，v等數(shù)組，空間復(fù)雜度是O(nm)。計算f，u，v的時間復(fù)雜度是O(nm)，因此總的時間復(fù)雜度也還是O(nm)。Codes (IOI 1999) 1. 碼字集合 2. 一個文本，碼字埋藏在文本之中求文本能覆蓋的碼字長度之和最大。要求： 所