動(dòng)態(tài)規(guī)劃總結(jié)

1、DP的復(fù)習(xí)與提高,,最長不下降子序列模型,設(shè)有整數(shù)序列b1,b2,b3,……,bn, 若存在i1<i2<i3<……<im, 且bi1<bi2<bi3……<bim, 則稱b1,b2,b3,……,bn,中有長度為M的不下降序列bi1，bi2，bi3，……，bim。求序列b1,b2,b3,……,bn中所有長度（M）最大不下降序列。輸入：整數(shù)序列輸出：最大長度M和所有長度為M的序列個(gè)數(shù)T,分析:,

2、設(shè)h[1..n]表示n個(gè)輸入的整數(shù)；令f[i]表示從第i個(gè)數(shù)開始到第m個(gè)數(shù)的最長不下降子序列的長度，則有：f[i] = max(f[j]+1)(1<=i<=n-1, i+1<=j<=n, h[i]<=h[j])邊界為f[n] := 1具體求解時(shí)用倒推，for i:=n-1 downto 1時(shí)間復(fù)雜性：O(n2),順推的算法,設(shè)f(i)為前i個(gè)數(shù)中的最大不下降序列長度 , 則f(i)=max{f(

3、j)+1} (1<=j<i<=n, h[j]<h[i])邊界為F(1)=1下面的優(yōu)化算法是以順推方向進(jìn)行的.,優(yōu)化,如果當(dāng)n<=100000時(shí)，顯然上述算法要超時(shí)。從DP的基本優(yōu)化思路著手，也就是去除一些一定不會(huì)有最優(yōu)解產(chǎn)生的狀態(tài)。例如：f[i]=3; h[i]=10; f[j]=3; h[j]=5,那么無論具體的搭配情況如何，狀態(tài)j都要比狀態(tài)i優(yōu)秀。也就是說，我們只需要保留當(dāng)前長度為i的序列中最后

4、一個(gè)數(shù)字即可，并且這個(gè)數(shù)是所有長度為i的不下降序列中最后一個(gè)數(shù)的最小值。,由此，算法的本質(zhì)也發(fā)生了變化。設(shè)b[i]表示長度為i的不下降序列的最后一個(gè)元素的最小值。初始化：b[i]:=maxlongint, b[1] := h[1]容易看出，b數(shù)組一定是不下降序列。當(dāng)處理h[i]時(shí)，用二分法查找它可以連接到長度最大為多少的不下降子序列的之后（查找區(qū)間的左右邊界是1~i）。假設(shè)可以連到長度最大為y的不上升子序列后，則b[y+1]:

5、=min{b[y+1],h[i]}。在找到h[i]的最終位置后,也就知道了前i個(gè)數(shù)的最長不下降序列的長度了,這時(shí)就可記錄f[i]的值.最后，b數(shù)組被賦值的元素最大下標(biāo)就是問題的答案。在實(shí)現(xiàn)時(shí)要仔細(xì)考慮一些細(xì)節(jié)情況.,1.求最長不下降序列參考程序:const maxn=100000;var h,b,f:array[1..maxn] of longint; n,i,j,k,l,r,m:longint; found :

6、boolean;begin readln(n); for i:=1 to n do read(h[i]); for i:=1 to n do b[i] := maxlongint; b[1] := h[1]; f[1] := 1; for i:=2 to n do begin l:=1; r:= i; while l h[i] then begin b[l] := h[i];

7、 f[i] := l; end,else f[i] := l+1; end; j:=0; for i:=1 to n do if b[i] maxlongint then inc(j) else break; writeln(j); for i:=1 to j do write(b[i]:4); writeln; for i:=1 t

8、o n do write(f[i]:4);end.數(shù)據(jù)f存儲(chǔ)了以每個(gè)元素結(jié)尾的最長不下降序列的長度.,注意：兩個(gè)程序的主要區(qū)別在于二分查找時(shí)對(duì)于b[m]=h[i]時(shí)的處理方法不同。對(duì)于嚴(yán)格遞增序列來說，出現(xiàn)相等時(shí)，不增加序列長度。對(duì)于不降序列來說，則要增加序列長度。,2. 求嚴(yán)格遞增序列const maxn=100000;var h,b,f:array[1..maxn] of longint; n,i,j,k,

9、l,r,m:longint; found :boolean;begin readln(n); for i:=1 to n do read(h[i]); for i:=1 to n do b[i] := maxlongint; b[1] := h[1]; f[1] := 1; for i:=2 to n do begin l:=1; r:= i; found := false; w

10、hile l h[i] then r := m-1 else if b[m] < h[i] then l := m+1 else begin found := true; f[i] := m; break; end;,end; if found = false then if b[l] >

11、 h[i] then begin b[l] := h[i]; f[i] := l; end else begin b[l+1] := h[i]; f[i] := l+1; end end; j:=0; for i:=1 to n do if b[i] maxlongint then inc(j)

12、else break; writeln(j); for i:=1 to j do write(b[i]:4); writeln; for i:=1 to n do write(f[i]:4);end.,最長不下降序列拓展,1、求序列中最長不下降序列的個(gè)數(shù)。 設(shè)t[i]為以i結(jié)尾的最長不下降序列的個(gè)數(shù),則T[i]=∑t[j] (1<=j<i<=n , h[j]<=

13、h[i], f[i]=f[j]+1) 邊界為:t[1]=1當(dāng)f[i]=n時(shí)，將t[i]累加舉例： h: 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時(shí)，個(gè)數(shù)為∑t=4,最長不下降序列拓展,2、求本質(zhì)不同的最長不下降序列的個(gè)數(shù)。(注:其實(shí)這

14、里討論的是單調(diào)遞增序列)求本質(zhì)不同的最長不下降序列個(gè)數(shù)有多少個(gè)？如：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ì)不同的。但對(duì)于 h 1 2 2 3 3 5 4 5 f 1 2 2 3 3 4 4 4

15、 t 1 1 1 2 2 4 4 4 答案有8個(gè)，其中4個(gè)1 2 3 5 ，4個(gè)1 2 3 4正確答案應(yīng)該是兩個(gè).,上例顯然對(duì)于原序列h中兩個(gè)相同的數(shù)，重復(fù)算了多次因此，我們對(duì)算法進(jìn)行改進(jìn)：對(duì)原序列按h從小到大（當(dāng)h[i]=h[j]時(shí)按F從大到?。┡判?，增設(shè)Order[i]記錄新序列中的i個(gè)數(shù)在原序列中的位置?？梢?，求t[i]時(shí)，當(dāng)f[j]=f[j+1],h[j]=h[j+1]且Order[j+1]

16、h[j]),則下面的數(shù)據(jù)又會(huì)出現(xiàn)錯(cuò)誤答案: h 1 3 4 5 1 2 3 5 f 1 2 3 4 1 2 3 4 程序輸出為1正確應(yīng)該是2,錯(cuò)誤程序1: 按PPT中的算法執(zhí)行const maxn=10000;var h,f,t,order:array[1..maxn] of longint; n,i,j,k,max, mlen:long

17、int;procedure swap(var a,b:longint);var x:longint;begin x:= a; a:=b; b:=x;end;begin readln(n); for i:=1 to n do read(h[i]); mlen:=0; for i:=1 to n do begin read(f[i]); if f[i] > mlen then

18、 mlen := f[i]; end; for i:=1 to n+1 do order[i] := i; h[n+1] := maxlongint; f[n+1] := mlen+1; inc(n);,for i:=1 to n-1 do for j:=n downto i+1 do if h[j-1] > h[j] then begin swap(h[j-1],h

19、[j]); swap(f[j-1],f[j]); swap(order[j-1],order[j]); end else if h[j-1] = h[j] then begin if f[j-1] < f[j] then begin swap(h[j-1],h[j]); swap(f[j-1],f[j]);

20、 swap(order[j-1],order[j]); end; end; t[1] := 1; for i:=2 to n do for j:= i-1 downto 1 do if (h[j] < h[i]) and (f[j]+1 = f[i]) then if not (( h[j]=h[j+1]) and (f[j]=f[j+1]) and(o

21、rder[j+1]<order[i])) then inc(t[i], t[j]);writeln(t[n]);end.,錯(cuò)誤程序2,按教材P224頁例8-3算法const maxn=10000;var h,f,t,order:array[1..maxn] of longint; n,i,j,k,max, mlen:longint;procedure swap(var a,b:longint)

22、;var x:longint;begin x:= a; a:=b; b:=x;end;begin readln(n); for i:=1 to n do read(h[i]); mlen:=0; for i:=1 to n do begin read(f[i]); if f[i] > mlen then mlen := f[i]; end; for i:=1

23、to n+1 do order[i] := i; h[n+1] := maxlongint; f[n+1] := mlen+1; inc(n);,for i:=1 to n do if f[i] = 1 then t[i] := 1; for k:=2 to mlen+1 do for i:=n downto 1 do if f[i] = k then begin j:=i-

24、1; while (j>0) and (h[j] h[i] ) do begin if (h[j] < h[i]) and (f[j]+1=k) then inc(t[i], t[j]); dec(j); end; end; writeln(t[n]);end.,到目前通過所有數(shù)據(jù)的程序:cons

25、t maxn=10000;var h,f,t,order:array[1..maxn] of longint; n,i,j,k,max, mlen:longint;procedure swap(var a,b:longint);var x:longint;begin x:= a; a:=b; b:=x;end;begin readln(n); for i:=1 to n do read(h[i])

26、; mlen:=0; for i:=1 to n do begin read(f[i]); if f[i] > mlen then mlen := f[i]; end; for i:=1 to n+1 do order[i] := i; h[n+1] := maxlongint; //建立哨兵 f[n+1] := mlen+1; inc(n);,t[1]:=1; //

27、前一個(gè)程序中僅有的改動(dòng) for k:=2 to mlen+1 do for i:=n downto 1 do if f[i] = k then begin j:=i-1; while (j>0) and (h[j] h[i] ) do begin if (h[j] < h[i]) and (f[j]+1=k) then

28、 inc(t[i], t[j]); dec(j); end; end; writeln(t[n]);end.,測(cè)試數(shù)據(jù)71 2 2 3 3 5 41 2 2 3 4 4 491 2 3 4 6 5 8 10 91 2 3 4 5 5 6 7 781 2 2 3 3 5 4 51 2 2 3 4 4 4 58 1 2 1 2 3 3 5 41 2 1

29、 2 3 3 4 4 81 3 4 5 1 2 3 51 2 3 4 1 2 3 4,但這組數(shù)據(jù)過不了:82 3 4 5 1 2 3 51 2 3 4 1 2 3 4,經(jīng)典賽題,1、導(dǎo)彈攔截（注意：第二問不可以用每次刪除最長不上升序列的方法做。比如，當(dāng)來襲的導(dǎo)彈共有4顆，高度依次為2 4 1 3的時(shí)候，如果不巧找到的最長不上升序列為4 1，那么剩下的2和3就只能另外啟用兩套系統(tǒng)了。這顯然不是最優(yōu)解。 ）第二問用貪心法即可

30、。每顆導(dǎo)彈來襲時(shí)，使用能攔截這顆導(dǎo)彈的防御系統(tǒng)中上一次攔截導(dǎo)彈高度最低的那一套來攔截。若不存在符合這一條件的系統(tǒng)，則使用一套新系統(tǒng)。,合唱隊(duì)形,【問題描述】N位同學(xué)站成一排，音樂老師要請(qǐng)其中的(N-K)位同學(xué)出列，使得剩下的K位同學(xué)排成合唱隊(duì)形。合唱隊(duì)形是指這樣的一種隊(duì)形：設(shè)K位同學(xué)從左到右依次編號(hào)為1, 2, …, K，他們的身高分別為T1, T2, …, TK，則他們的身高滿足T1 Ti+1 > … > TK (1≤

31、i≤K)。你的任務(wù)是，已知所有N位同學(xué)的身高，計(jì)算最少需要幾位同學(xué)出列，可以使得剩下的同學(xué)排成合唱隊(duì)形。,輸入文件    輸入文件chorus.in的第一行是一個(gè)整數(shù)N(2<=N<=100)，表示同學(xué)的總數(shù)。第一行有n個(gè)整數(shù)，用空格分隔，第i個(gè)整數(shù)Ti(130<=Ti<=230)是第i位同學(xué)的身高(厘米)。- 輸出文件    

32、輸出文件chorus.out包括一行，這一行只包含一個(gè)整數(shù)，就是最少需要幾位同學(xué)出列。- 樣例輸入8186 186 150 200 160 130 197 220- 樣例輸出4,設(shè)有N*N的方格圖(N<=10,我們將其中的某些方格中填入正整數(shù),而其他的方格中則放入數(shù)字0。如下圖所示（見樣例）：,方格取數(shù)？（可以用最長不下降模型嗎？）對(duì)比VIJOS 飛翔,飛翔 http://mail.bashu.cn:8080/Judg

33、eOnline/showproblem?problem_id=1907,某人從圖的左上角的A 點(diǎn)出發(fā)，可以向下行走，也可以向右走，直到到達(dá)右下角的B點(diǎn)。在走過的路上，他可以取走方格中的數(shù)（取走后的方格中將變?yōu)閿?shù)字0）。此人從A點(diǎn)到B 點(diǎn)共走兩次，試找出2條這樣的路徑，使得取得的數(shù)之和為最大。  輸 入 輸入的第一行為一個(gè)整數(shù)N（表示N*N的方格圖），接下來的每行有三個(gè)整數(shù)，前兩個(gè)表示位置，第三個(gè)數(shù)為該位置上

34、所放的數(shù)。一行單獨(dú)的0表示輸入結(jié)束。  輸 出 只需輸出一個(gè)整數(shù)，表示2條路徑上取得的最大的和。,后面是另外思路的DP參考解答,分析:,這是一道所謂”路徑”類型的DP題.這道題的階段劃分方法有兩種:較為簡(jiǎn)單的一種是按行劃分階段,按列劃分狀態(tài).如果人只從A點(diǎn)到B點(diǎn)走一次,則可以用DP較方便的解決:從A開始,向下向下遞推,依次求出從A點(diǎn)出發(fā)到達(dá)當(dāng)前位置(i,j)所能取得的最大的數(shù)之和,存放在sum數(shù)組中

35、.原始數(shù)據(jù)存放在data數(shù)組中.為處理方便, sum數(shù)組加進(jìn)了0行和0列. 狀態(tài)轉(zhuǎn)移方程為:Sum[i,j] = max{sum[i-1,j], sum[i,j-1]} + data[i,j] (1<=i<=n, 1<=j<=n),如果走兩次,能不能夠用DP先走一次,求得最大數(shù)和, 把路徑上的數(shù)清0,然后再用DP走一次,求得第二最大數(shù)和,再把兩次的結(jié)果相加得到最后的結(jié)果呢?這是一種很自然的想法,并且對(duì)測(cè)試樣例也

36、是正確的.但實(shí)際這種算法是錯(cuò)誤的.例如,對(duì)右圖數(shù)據(jù),若按DP先走一次,將取完紅色字體的數(shù),但第二次DP時(shí),兩個(gè)黑色的數(shù)字將無法同時(shí)取到.而事實(shí)我們可以簡(jiǎn)單地將第3列和第5列的所有數(shù)取完.因此本題所謂走兩次其實(shí)必須在一次DP時(shí)同時(shí)考察兩條路徑.,考慮兩個(gè)人同時(shí)從A出發(fā),則需要考慮兩個(gè)人到達(dá)任意兩個(gè)格子(i1,j1)(i2,j2)的情況.即狀態(tài)要用4個(gè)變量來描述:sum[i1,j1,i2,j2]每個(gè)人可以從上或左的兩個(gè)方向達(dá)到當(dāng)前

37、格子,顯然前一狀態(tài)必為:(i1-1,j1), (i2-1,j2)(i1-1,j1),(i2, j2-1)(i1,j1-1),(i2-1,j2)(i1,j1-1),(i2,j2-1)四種情況之一.設(shè)p=max{sum[i1-1,j1, i2-1,j2], sum[i1-1,j1,i2, j2-1], sum[i1,j1-1,i2-1,j2],sum[i1,j1-1,i2,j2-1]}則有,據(jù)此,可寫出程序.易知,本算法的時(shí)間

38、空間復(fù)雜度均為O(n^4)后一段分析是按對(duì)角線方向來劃分階段的.這樣處理之后, 可以把時(shí)間復(fù)雜性降低一維,把空間復(fù)雜性降低到O(n^2), 因此該思想方法要認(rèn)真思考, 掌握,優(yōu)化方法: 1、狀態(tài)的設(shè)計(jì) 對(duì)于本題來說，狀態(tài)的選定和存儲(chǔ)對(duì)整個(gè)問題的處理起了決定性的作用。我們從（1，1）出發(fā)，每走一步作為一個(gè)階段，則可以分成2*n-1個(gè)階段： 第一個(gè)階段，兩條路徑從（1，1）出發(fā)； 第二個(gè)階段，兩條路徑可達(dá)（2，1）

39、和（1，2）； 第三個(gè)階段，兩條路徑可達(dá)的位置集合為（3，1）、（2，2）和（1，3）； ………………………… 第2*n-1個(gè)階段，兩條路徑匯聚（n，n）；在第k(1≤k≤2*n-1)個(gè)階段，兩條路徑的終端坐標(biāo)（x1，y1）（x2，y2）位于對(duì)應(yīng)的右下對(duì)角線上。如下圖所示：,,如果我們將兩條路徑走第i步的所有可能位置定義為當(dāng)前階段的狀態(tài)的話，面對(duì)的問題就是如何存儲(chǔ)狀態(tài)了。方格取數(shù)問題的狀態(tài)數(shù)目十分龐大，每一個(gè)

40、位置是兩維的，且又是求兩條最佳路徑，這就要求在存儲(chǔ)上必須做一定的優(yōu)化后才有可能實(shí)現(xiàn)算法的程序化。主要的優(yōu)化就是：舍棄一切不必要的存儲(chǔ)量。為此，我們?nèi)∥恢弥械膞坐標(biāo)（x1，x2）作狀態(tài)，其中（1≤x1≤n）and（1≤x2≤n））直接由x坐標(biāo)計(jì)算對(duì)應(yīng)的y坐標(biāo)：（y1=k+1-x1）and（y1∈{1‥n}）and（y2=k+1-x2）and（y2∈{1‥n},,2、狀態(tài)轉(zhuǎn)移方程設(shè)兩條路徑在k階段的狀態(tài)為（x1，x2）。由（y1=

41、k+1-x1）∧（y1 ∈{1..n}）得出第一條路徑的坐標(biāo)為（x1，y1）；由（y2=k+1-x2）∧（y2 ∈{1..n}）得出第二條路徑的坐標(biāo)為（x2，y2）。假設(shè)在k-1階段，兩條路徑的狀態(tài)為（x1’，x2’）且（x1’，x2’）位于（x1，x2）狀態(tài)的左鄰或上鄰位置。因此我們?cè)O(shè)兩條路徑的延伸方向?yàn)閐1和d2：di=0，表明第i條路徑由（xi’，yi’）向右延伸至（xi，yi）；di=1，表明第i條路徑由（xi’，yi

42、’）向下延伸至（xi，yi）（1≤i≤2）。顯然（x1’= x2’）∧（d1= d2），表明兩條路徑重合，同時(shí)取走了（x1’，y1’）和（x1，y1）中的數(shù)，這種取法當(dāng)然不可能得到最大數(shù)和的。分析兩種可能：⑴若x1=x2，則兩條路徑會(huì)合于x1狀態(tài)，可取走（x1，y1）中的數(shù)(如下圖)； x2’(x1’) x1’(x2’) x1=x2,,,,⑵若

43、x1≠x2，則在k階段，第一條路徑由x1’狀態(tài)延伸至x1狀態(tài)，第二條路徑由x2’狀態(tài)延伸至x2狀態(tài)，兩條路徑可分別取走（x1，y1）和（x2，y2）中的數(shù)(如下圖)；,X1’→X1,X2’↓X2,設(shè) f[k，x1，x2]—在第k階段，兩條路徑分別行至x1狀態(tài)和x2狀態(tài)的最大數(shù)和。顯然k=1時(shí)，f[1，1，1]=data[1,1]；k≥2時(shí)，f[k，x1，x2]=max{f[k-1， x1’，x2’]+data[x1，y1](

44、x1=x2)，f[k-1， x1’，x2’]+data[x1，y1]+data[x2，y2](x1≠x2)} 1≤k≤2*n-1，x1’可達(dá)x1的狀態(tài)集合，x2’可達(dá)x2的狀態(tài)集合，（x1’≠x2’）∨(d1≠d2)；上述狀態(tài)轉(zhuǎn)移方程符合最優(yōu)子結(jié)構(gòu)和重疊子問題的特性，因此適用于動(dòng)態(tài)程序設(shè)計(jì)方法求解。由于第k個(gè)階段的狀態(tài)轉(zhuǎn)移方程僅與第k-1個(gè)階段的狀態(tài)發(fā)生聯(lián)系

45、，因此不妨設(shè) f0—第k-1個(gè)階段的狀態(tài)轉(zhuǎn)移方程； f1—第k個(gè)階段的狀態(tài)轉(zhuǎn)移方程；初始時(shí)，f0[1，1]=0。經(jīng)過2*n-1個(gè)階段后得出的f0[n，n]即為問題的解。此為空間優(yōu)化！,3、多進(jìn)程決策的動(dòng)態(tài)程序設(shè)計(jì) 由于方格取數(shù)問題是對(duì)兩條路徑進(jìn)行最優(yōu)化決策的，因此稱這類動(dòng)態(tài)程序設(shè)計(jì)為分階段、多進(jìn)程的最優(yōu)化決策過程。設(shè)階段i：準(zhǔn)備走第i步（1≤i≤2*n-1）；狀態(tài)（x1，x2）： 第i步的狀態(tài)號(hào)（1≤x

46、1，x2≤i。x1，x2∈{1..n}）決策（d1，d2）：第一條路徑由x1狀態(tài)出發(fā)沿d1方向延伸、第二條路徑由x2狀態(tài) 出發(fā)沿d2方向延伸，可使得兩條路徑的數(shù)和最大（0≤d1，d2≤1。方向0表示右移，方向1表示下移）；本題的啟示:1.如果某個(gè)狀態(tài)變量可以由另一個(gè)狀態(tài)變量計(jì)算產(chǎn)生(例如y坐標(biāo)可由x坐標(biāo)計(jì)算生成),則這個(gè)狀態(tài)變量可以不保存;這樣可以壓縮狀態(tài).2.如果K階段的狀態(tài)只與K-1階段的狀態(tài)值有關(guān),則可以利用滾動(dòng)數(shù)組,只保

47、留前后兩個(gè)階段的狀態(tài)值.初值狀態(tài)值保存在F0中,然后由F0去遞推計(jì)算F1,每次計(jì)算完成后,又將F1的值賦值到F0中,以便下一階段的計(jì)算.,fillchar(f0，sizeof(f0)，0)；{行走前的狀態(tài)轉(zhuǎn)移方程初始化}f0[1，1]←data[1,1]；for i←2 to 2*n-1 do{階段：準(zhǔn)備走第i步} begin fillchar(f1，sizeof(f1)，0)；{ 走第i步的狀態(tài)轉(zhuǎn)移方程初始化} for

48、 x1←1 to i do{枚舉兩條路徑在第i-1步時(shí)的狀態(tài)x1’和x2’} for x2←1 to i do begin 計(jì)算y1和y2； if (x1，y1)和(x2，y2)在界內(nèi) then for d1←0 to 1 do {決策：計(jì)算兩條路徑的最佳延伸方向} for d2←0 to 1 do,begin 第1條路徑沿d1方向延伸至(x1’，y1’）； 第

49、2條路徑沿d2方向延伸至(x2’，y2’)； if (x1’，y1’)和(x2’，y2’)在界內(nèi) {計(jì)算第i步的狀態(tài)轉(zhuǎn)移方程}then f1[x1，x2]←max{f0[x1’，x2’]+data[x1，y1]∣x1=x2，f0[x1’，x2’]+data[x1，y1]+data[x2，y2]∣x1≠x2} end；{for} end；{for} f0←f1；{記下第i步的狀態(tài)轉(zhuǎn)

50、移方程}end；{for}輸出兩條路徑取得的最大數(shù)和f0[n，n],const maxn=20; dir:array[1..2,1..2] of integer= ((-1,0), (0,-1));var a, f0,f1:array[0..maxn,0..maxn] of integer; n, i,j,k,d1,d2:integer; x1,y1, x2, y2,x1p,y1p, x2p, y2p,

51、max:integer;begin readln(n); readln(i,j,k); while not ((i=0) and (j=0) and (k=0)) do begin a[i,j] := k; readln(i,j,k); end; f0[1,1] := a[1,1]; for k:=2 to 2*n -1 do begin fillchar(f1, sizeof(f1),

52、0); for x1:=1 to k do begin y1:=k+1-x1; if (x1<=n) and (1<=y1) and (y1<=n) then begin for x2:=1 to k do begin y2:=k+1-x2;,if (x2 max then max := f0[x1p,x2p];

53、 end; if (x1=x2) and (y1=y2) then f1[x1,x2] := max + a[x1,y1] else f1[x1,x2] := max + a[x1,y1] + a[x2,y2]; end; end; end;

54、end; f0:=f1; end; writeln(f0[n,n]);end.,類似題目: Vijos P1143 三取方格數(shù),數(shù)塔模型,如下所示一個(gè)數(shù)字三角形 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5寫一個(gè)程序計(jì)算從頂至底的某處的一條路徑，使該路徑所經(jīng)過的數(shù)字和最大每一步可沿直向下或 右斜線向下走1<三角形行數(shù)<

55、=100三角形中的數(shù)字為整數(shù)0，1，，，99,分析: 設(shè)：f[i,j]為從第i行中的第j個(gè)數(shù)至第n行的最大的數(shù)字和；則: f[n,j]=a[n,j]  ( 1<=j<=n )    f[i,j]=max{f[i+1,j] , f[i+ 1,j+1]}  + a[i,j] (1<=j<=i, 1<=i<=n-1) 

56、0;  f[1,1]即為所求。經(jīng)典例題: 花店櫥窗布置參見教材P230 例8-5On the Web:http://web.zjdyzx.com/doj/showproblem.asp?problem_id=1101,【題目描述】    假設(shè)你想以最美觀的方式布置花店的櫥窗。現(xiàn)在你有F束不同品種的花束，同時(shí)你也有至少同樣數(shù)量的花瓶被按順序擺成一行。這些花瓶的位置固定于架子上，并從1至V順

57、序編號(hào)，V是花瓶的數(shù)目，從左至右排列，則最左邊的是花瓶1，最右邊的是花瓶V?；ㄊ梢砸苿?dòng)，并且每束花用1至F間的整數(shù)唯一標(biāo)識(shí)。標(biāo)識(shí)花束的整數(shù)決定了花束在花瓶中的順序，如果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ù)的順序，即：杜鵑花必須放在秋海棠左邊的花瓶中，秋海棠必須放在康乃

58、馨左邊的花瓶中。如果花瓶的數(shù)目大于花束的數(shù)目。則多余的花瓶必須空置，且每個(gè)花瓶中只能放一束花。 每一個(gè)花瓶都具有各自的特點(diǎn)。因此，當(dāng)各個(gè)花瓶中放入不同的花束時(shí)，會(huì)產(chǎn)生不同的美學(xué)效果，并以美學(xué)值（一個(gè)整數(shù)）來表示，空置花瓶的美學(xué)值為零。在上述例子中，花瓶與花束的不同搭配所具有的美學(xué)值，如下表所示。,花 瓶 1 2 3

59、 4 5 1 (杜鵑花) 7 23 -5 -24 16 2 (秋海棠) 5 21 -4 10 23 3 (康乃馨) -21 5

60、 -4 -20 20例如，根據(jù)上表，杜鵑花放在花瓶2中，會(huì)顯得非常好看；但若放在花瓶4中則顯得十分難看。       為取得最佳美學(xué)效果，你必須在保持花束順序的前提下，使花束的擺放取得最大的美學(xué)值。如果有不止一種的擺放方式具有最大的美學(xué)值，則其中任何一直擺放方式都可以接受，但你只要輸出任意一種擺放方式。（2）假設(shè)條件 

61、0;    1≤F≤100，其中F為花束的數(shù)量，花束編號(hào)從1至F。      F≤V≤100，其中V是花瓶的數(shù)量。      -50≤Aij≤50，其中Aij是花束i在花瓶j中的美學(xué)值。,（3）輸入 第一行包含兩個(gè)數(shù)：F，V。 隨后的F行中，每行包含V個(gè)整數(shù)，Aij 即為輸入文件中

62、第（i+1 ）行中的第j個(gè)數(shù)。（4）輸出一行，表示程序所產(chǎn)生擺放方式的美學(xué)值。樣例輸入：3 5 7 23 -5 -24 165 21 -4 10 23-21 5 -4 -20 20樣例輸出：53,分析: 將問題進(jìn)行轉(zhuǎn)化，找出問題的原型。將擺放方案的要求用表格表現(xiàn)出來，則擺放方案需要滿足：（1）每行選且只選一個(gè)數(shù)（花瓶），（2）擺放方案的相鄰兩行中，下面一行的花瓶編號(hào)要大于上面一行的花瓶編號(hào)。這樣

63、可將問題轉(zhuǎn)化成：給定一個(gè)數(shù)字表格，求解從頂行至底行的一條路徑，使得這條路徑所經(jīng)過的數(shù)字總和最大，要求滿足兩個(gè)條件：（1）每行選且僅選一個(gè)數(shù)字；（2）路徑中相鄰兩行數(shù)字，必須保證下一行數(shù)字的列數(shù)大于上一行數(shù)字的列數(shù)。對(duì)比數(shù)塔原型，寫出動(dòng)態(tài)規(guī)劃轉(zhuǎn)移方程。設(shè)b[i,j]表示美學(xué)值表格中第i行的第j個(gè)數(shù)字，用q[i,j]表示從表格最底層到b[i,j]這個(gè)數(shù)字的最佳路徑的數(shù)字和，F(xiàn)表示花束總數(shù)，V表示花瓶總數(shù)，則有：邊界： q[i, V+

64、1] := -∞ (1<=i<=F) q[F,j] := b[F,j] (1<=j<=V) 狀態(tài)轉(zhuǎn)移方程：q[i,j] := max{q[i+1, k]} (j+1<=k<=V+1) + b[i,j] (1<=i<=F-1, 1<=j<=V)這樣，得出的max{q[1,j]} (1<=j<=V)就是最大的美學(xué)值。算法復(fù)雜性為：

65、O（FV2）,優(yōu)化,看一下這樣兩個(gè)狀態(tài)的求解方法：q[i,j] = max{q[i+1,k]} (j+1<=k<=V+1) + b[i,j]q[i,j+1] = max{q[i+1,k]} (j+2<=k<=V+1)+b[i,j+1]上面兩個(gè)狀態(tài)中求max{q[i+1,k]}的過程中進(jìn)行了大量重復(fù)的比較，非常費(fèi)時(shí)。對(duì)狀態(tài)的表示作修改，用數(shù)組t[i,j]表示第i行從第j列起到V列的美學(xué)值的最大值，即：t[

66、i,j] = max{q[i,k] (j<=k<=V) } (1<=i<=F, 1<=j<=V)表示新的狀態(tài)。經(jīng)過修改后，因?yàn)閝[i,j] = t[i+1,j+1] + b[i,j], 而t[i,j] = max{t[i,j+1], q[i,j]} (1<=i<=F, 1<=j<=V)所以得出新的狀態(tài)轉(zhuǎn)移方程：t[F,j] = max {t[F,j+1], b[F,j]}

67、 (1<=j<=V)t[i,j] = max{t[i, j+1], t[i+1,j+1]+b[i,j] } (1<=j<=V, 1<=i<=F-1)這樣，得出的最大美學(xué)值為t[1,1]，新算法的時(shí)間復(fù)雜度為O(FV),最小代價(jià)子母樹模型,有n堆石子排成一條直線，每堆石子有一定的重量?，F(xiàn)在要合并這些石子成為一堆石子，但是每次只能合并相鄰的兩堆。每次合并需要消耗一定的體力，該體力為所合并的兩堆石子的

68、重量之和。問最少需要多少體力才能將n堆石子合并成一堆石子？數(shù)據(jù)規(guī)模:n<=3000樣例輸入: 8 5 2 4 7 6 1 3 9樣例輸出: 105,分析,令m[i,j]表示歸并第i個(gè)數(shù)到第j數(shù)的最小代價(jià),w[i,j]表示第i個(gè)數(shù)到第j個(gè)數(shù)的和，這個(gè)可以事先計(jì)算出來。w[i,j]可以在O(1)的時(shí)間內(nèi)算出.有如下的狀態(tài)轉(zhuǎn)移方程:,階段：以歸并石子的長度為階段，一共有n-1個(gè)階段。狀態(tài)：每個(gè)

69、階段有多少堆石子要?dú)w并，當(dāng)歸并長度為2時(shí)，有n-1個(gè)狀態(tài)；當(dāng)歸并長度為3時(shí)，有n-2個(gè)狀態(tài)；當(dāng)歸并長度為n時(shí)，有1個(gè)狀態(tài)。決策：當(dāng)歸并長度為2時(shí)，有1個(gè)決策；當(dāng)歸并長度為3時(shí)，有2個(gè)決策；當(dāng)歸并長度為n時(shí)，有n-1個(gè)決策。 for len := 2 to n do for i := 1 to n - len + 1 do begin j := i + len - 1;

70、 f[i,j] := MAXINT; for k:= i+1 to j do begin 參考上面狀態(tài)轉(zhuǎn)移方程求解,優(yōu)化,不難發(fā)現(xiàn)這個(gè)算法的復(fù)雜度是n^3。n的范圍是3000，需要優(yōu)化算法。對(duì)于動(dòng)態(tài)規(guī)劃的優(yōu)化和搜索的優(yōu)化是一樣的道理。搜索中，如果某狀態(tài)下不會(huì)有最優(yōu)解，那么就不用繼續(xù)搜索下去了。動(dòng)態(tài)規(guī)劃也可以這樣來優(yōu)化。具體方法是：在計(jì)算每個(gè)狀態(tài)的值的時(shí)候，記