【正文】 L:=0。 begin writeln(39。 下面找出最長(zhǎng)不下降序列： k:=1。k:=0。 ②從倒數(shù)第三項(xiàng)開(kāi)始其后有 2項(xiàng)，需做兩次比較，得到目前最長(zhǎng)的不下降序列為 2，如下表： 11 12 13 14 …… 11 12 13 14 22 63 15 …… 21 22 63 15 2 1 1 …… 3 2 1 1 13 0 0 …… 12 13 0 0 ㈤ 一般處理過(guò)程是： ①在 i+1,i+2,…,n 項(xiàng)中，找出比 b[I,1]大的最長(zhǎng)長(zhǎng)度 L以及位置 K。 ②若 b(n1)b(n)則存在長(zhǎng)度為 1的不下降序列 b(n1)或 b(n)。 end. 【 例 3】 求最長(zhǎng)不下降序列 ㈠問(wèn)題描述： 設(shè)有由 n個(gè)不相同的整數(shù)組成的數(shù)列，記為 :b(1)、 b(2)、 …… 、 b(n)且b(i)b(j) (ij)，若存在 i1i2i3 … ie 且有 b(i1)b(i2) … b(ie) 則稱(chēng)為長(zhǎng)度為 e的不下降序列。 b[1,1] := a[1,1]。N = 39。因此本題是一個(gè)典型的多階段決策最優(yōu)化問(wèn)題。 39。 for x:=n1 downto 1 do for y:=1 to x do if a[x+1,y,2]a[x+1,y+1,2] then //選擇路徑，保留最大路徑值 begin a[x,y,2]:=a[x,y,2]+a[x+1,y,2]。 x,y,n:integer。 【 解法一 】 （逆推法） 【 算法分析 】 ① 貪心法往往得不到最優(yōu)解：本題若采用貪心法則： 1311121413，其和為 63,但存在另一條路： 138261524，其和為 86。同樣的道理下一層的走向又要取決于再下一層上的最大值是否已經(jīng)求出才能決策。我們?cè)诟?jìng)賽中碰到的大多是最優(yōu)化問(wèn)題，而動(dòng)態(tài)規(guī)劃正是解決最優(yōu)化問(wèn)題的有力武器，因此動(dòng)態(tài)規(guī)劃在競(jìng)賽中的地位日益提高。 f[5,1] := 0。 d[3,1,2] := 6。 d[1,1,1] := 5。 確定決策并寫(xiě)出狀態(tài)轉(zhuǎn)移方程 因?yàn)闆Q策和狀態(tài)轉(zhuǎn)移有著天然的聯(lián)系，狀態(tài)轉(zhuǎn)移就是根據(jù)上一階段的狀態(tài)和決策來(lái)導(dǎo)出本階段的狀態(tài)。在例題 1最短路徑問(wèn)題中，問(wèn)題被劃分成各個(gè)階段之后，階段 K中的狀態(tài)只能由階段 K+1中的狀態(tài)通過(guò)狀態(tài)轉(zhuǎn)移方程得來(lái)，與其它狀態(tài)沒(méi)有關(guān)系，特別與未發(fā)生的狀態(tài)沒(méi)有關(guān)系，例如從 Ci到 E的最短路徑，只與 Ci的位置有關(guān)，它是由 Di中的狀態(tài)通過(guò)狀態(tài)轉(zhuǎn)移方程得來(lái)，與 E狀態(tài)，特別是 A到 Ci的路徑選擇無(wú)關(guān)，這就是無(wú)后效性。 ? 最優(yōu)化原理與無(wú)后效性 上面已經(jīng)介紹了動(dòng)態(tài)規(guī)劃模型的基本組成，現(xiàn)在需要解決的問(wèn)題是：什么樣的“多階段決策問(wèn)題”才可以采用動(dòng)態(tài)規(guī)劃的方法求解。即從該階段的每一個(gè)狀態(tài)出發(fā)，通過(guò)一次選擇性的行動(dòng)轉(zhuǎn)移至下一階段的相應(yīng)狀態(tài)。 在上例的多階段決策問(wèn)題中，各個(gè)階段采取的決策，一般來(lái)說(shuō)是與階段有關(guān)的，決策依賴(lài)于當(dāng)前狀態(tài)，又隨即引起狀態(tài)的轉(zhuǎn)移，一個(gè)決策序列就是在變化的狀態(tài)中產(chǎn)生出來(lái)的，故有“動(dòng)態(tài)”的含義，我們稱(chēng)這種解決多階段決策最優(yōu)化的過(guò)程為動(dòng)態(tài)規(guī)劃程序設(shè)計(jì)方法。如下圖所示： 多階段決策過(guò)程，是指這樣的一類(lèi)特殊的活動(dòng)過(guò)程，問(wèn)題可以按時(shí)間順序分解成若干相互聯(lián)系的階段，在每一個(gè)階段都要做出決策，全部過(guò)程的決策是一個(gè)決策序列。第九章 動(dòng)態(tài)規(guī)劃 第一節(jié) 動(dòng)態(tài)規(guī)劃的基本模型 第二節(jié) 動(dòng)態(tài)規(guī)劃與遞推 第三節(jié) 歷屆 NOIP動(dòng)態(tài)規(guī)劃試題 第四節(jié) 背包問(wèn)題 第五節(jié) 動(dòng)態(tài)規(guī)劃應(yīng)用舉例 動(dòng)態(tài)規(guī)劃程序設(shè)計(jì)是對(duì)解最優(yōu)化問(wèn)題的一種途徑、一種方法，而不是一種特殊算法。要使整個(gè)活動(dòng)的總體效果達(dá)到最優(yōu)的問(wèn)題，稱(chēng)為多階段決策問(wèn)題。 ? 動(dòng)態(tài)規(guī)劃的基本概念和基本模型構(gòu)成 現(xiàn)在我們來(lái)介紹動(dòng)態(tài)規(guī)劃的基本概念。一個(gè)實(shí)際問(wèn)題可能要有多次決策和多個(gè)決策點(diǎn)，在每一個(gè)階段的每一個(gè)狀態(tài)中都需要有一次決策，決策也可以用變量來(lái)描述，稱(chēng)這種變量為決策變量。 一般來(lái)說(shuō)，能夠采用動(dòng)態(tài)規(guī)劃方法求解的問(wèn)題，必須滿(mǎn)足最優(yōu)化原理和無(wú)后效性原則： 動(dòng)態(tài)規(guī)劃的最優(yōu)化原理。 由此可見(jiàn)，對(duì)于不能劃分階段的問(wèn)題，不能運(yùn)用動(dòng)態(tài)規(guī)劃來(lái)解；對(duì)于能劃分階段，但不符合最優(yōu)化原理的，也不能用動(dòng)態(tài)規(guī)劃來(lái)解；既能劃分階段，又符合最優(yōu)化原理的，但不具備無(wú)后效性原則，還是不能用動(dòng)態(tài)規(guī)劃來(lái)解；誤用動(dòng)態(tài)規(guī)劃程序設(shè)計(jì)方法求解會(huì)導(dǎo)致錯(cuò)誤的結(jié)果。所以如果確定了決策，狀態(tài)轉(zhuǎn)移方程也就可以寫(xiě)出。 d[1,1,2] := 3。 d[3,2,1] := 5。 for i := 4 downto 1 do for j := 1 to 4 do for k := 1 to 4 do if d[i,j,k] 0 then if f[i,j] d[i,j,k]+f[i+1,k] then f[i,j] := d[i,j,k]+f[i+1,k]。而遞推法在處理判定性問(wèn)題和計(jì)數(shù)問(wèn)題方面也是一把利器。這樣一層一層推下去，直到倒數(shù)第二層時(shí)就非常明了。 貪心法問(wèn)題所在：眼光短淺。 begin write( 39。 a[x,y,3]:=0 end else begin a[x,y,2]:=a[x,y,2]+a[x+1,y+1,2]。)。在本題中僅要求輸出最優(yōu)解，為此我們?cè)O(shè)置了數(shù)組 A[i,j]保存三角形數(shù)塔， B[i,j]保存狀態(tài)值，按從上往下方式進(jìn)行求解。)。 for i := 2 to n do //選擇路徑，保留最大路徑值 for j := 1 to i do if b[i1,j1] b[i1,j] then b[i,j] := b[i1,j1]+b[i,j] else b[i,j] := b[i1,j]+b[i,j]。程序要求，當(dāng)原數(shù)列出之后，求出最長(zhǎng)的不下降序列。 3 ② 若 L0，則 b[I,2]:=L+1。 for j:=i+1 to n do if(b[j,1]b[i,1])and(b[j,2]L) then begin L:=b[j,2]。 for j:=1 to n do if b[j,2]b[k,2] then k:=j。input n:39。k:=0。 k:=1。 writeln。 輸入： N顆依次飛來(lái)的導(dǎo)彈高度，（導(dǎo)彈個(gè)數(shù) =1000）。 //初始化，讀入數(shù)據(jù) while not eoln do begin //eoln：行結(jié)束標(biāo)志 inc(n)。 for j := i+1 to n do //枚舉決策，計(jì)算最佳方案中攔截的下一枚導(dǎo)彈 if (a[j] = a[i]) and (b[j] max) then begin max := b[j]。 k := i。 readln。容易看出，這個(gè)數(shù)組是遞減的（當(dāng)然可能有相鄰兩個(gè)元素相等）。 【 參考程序 】 （順推法） program tju1004。 b[i]:=max+1。 until seekeof。 var a:array[1..100,1..100] of integer。)。c[i]:=x end。 close(input)。設(shè) W(i)為第 i個(gè)地窖所藏有的地雷數(shù)， A（ i,j）表示第 i個(gè)地窖與第 j個(gè)地窖之間是否有通路， F(i)為從第 i個(gè)地窖開(kāi)始最多可以挖出的地雷數(shù)，則有如下遞歸式： F(i)=MAX { W(i)+ F(j) } (ij=n , A(i,j)=true) 邊界： F(n)=W(n) 于是就可以通過(guò)遞推的方法，從后 F(n)往前逐個(gè)找出所有的 F(i)，再?gòu)闹姓乙粋€(gè)最大的即為問(wèn)題 2的解。39。 fillchar(f,sizeof(f),0)。 //從后 F(n)往前逐個(gè)找出所有的 F(i) for i:=n1 downto 1 do begin L:=0。 k:=1。 k:=f[k,2]。由于河終年有霧，政府決定允許開(kāi)通的航線(xiàn)就互不交叉（如果兩條航線(xiàn)交叉，將有很大機(jī)會(huì)撞船）。 【 輸入輸出樣例 】 30 4 5 4 5 2 4 5 2 1 3 3 1 3 【 算法分析 】 我們將每對(duì)友好城市看成一條線(xiàn)段，則這道題的描述化為：有 N條線(xiàn)段，問(wèn)最少去掉多少條線(xiàn)，可以使剩下的線(xiàn)段互不交叉？ 第一，以北岸為線(xiàn)的起點(diǎn)而南岸為線(xiàn)的終點(diǎn)；先將所有的線(xiàn)按照起點(diǎn)坐標(biāo)值從小到大排序，按照每條線(xiàn)的終點(diǎn)坐標(biāo)計(jì)算交叉數(shù)：求線(xiàn) I的交叉數(shù) J[I]，則檢查所有 1..I1條線(xiàn)，若線(xiàn) J( 1= J I)的終點(diǎn)值大于線(xiàn) I的終點(diǎn)值，則線(xiàn) I與線(xiàn) J相交。這就把題目轉(zhuǎn)化為一個(gè)非常典型的動(dòng)態(tài)規(guī)劃題目了。例如： (N=10， M=10)， (1， 5)(起點(diǎn) )， (3，5)(終點(diǎn) )。 如此一來(lái)，狀態(tài)轉(zhuǎn)移關(guān)系便凸顯出來(lái)。 //輸入６種砝碼的個(gè)數(shù) n[0]:=1。 writeln(‘Total=’,n[0]1)。初始時(shí)， f[0， 0]=true（ 1≤i≤n，box[i]≤j≤v）。 //i階段的狀態(tài)轉(zhuǎn)移方程初始化 if x[i]v then continue。 end。 【 算法分析 】 我們按照由左而右和由右而左的順序，將 n個(gè)同學(xué)的身高排成數(shù)列。 //讀每個(gè)學(xué)生的身高 fillchar(b,sizeof(b),0)。 max:=0。 writeln(nmax+1)。 //身高滿(mǎn)足遞增順序的兩個(gè)隊(duì)列初始化 for i:=1 to n do //按照由左而右的順序計(jì)算 b序列 begin b[i]:=1。設(shè) a 為身高序列，其中 a[i]為同學(xué) i的身高； b 為由左而右身高遞增的人數(shù)序列，其中 b[i]為同學(xué) 1‥ 同學(xué) i間（包括同學(xué) i）身高滿(mǎn)足遞增順序的最多人數(shù)。 合唱隊(duì)形是指這樣的一種隊(duì)形：設(shè) K位同學(xué)從左到右依次編號(hào)為 1, 2, …, K ，他們的身高分別為 T1, T2, …, TK ，則他們的身高滿(mǎn)足 T1 T2 … Ti , Ti Ti+1 … TK (1≤i≤K) 。 //若物品 i裝入箱子后的體積正好為 j,則物品 i裝入箱子 f0:=f1。因此設(shè) f0為 i1階段的狀態(tài)轉(zhuǎn)移方程， f1為 i階段的狀態(tài)轉(zhuǎn)移方程，這樣可以將二維數(shù)組簡(jiǎn)化成一維數(shù)組。 要求從 n個(gè)物品中，任取若干個(gè)裝入箱內(nèi)，使箱子的剩余空間為最小。 //產(chǎn)生第１種重量０ for i:=1 to 6 do //階段：分析第 i種砝碼 for j:=1 to n[0] do //狀態(tài)：枚舉現(xiàn)有的不同重量 for k:=1 to a[i] do //決策：在現(xiàn)有重量的基礎(chǔ)上放 k塊第 i種砝碼｝ begin total:=n[j]+k*num[i]。由于棋盤(pán)規(guī)模的上限為 50*50，可能導(dǎo)致路徑數(shù)目大得驚人，因此不妨設(shè) map數(shù)組的元素類(lèi)型為 extended。只要將起點(diǎn)（ 1， 1）和終點(diǎn)（ n， m）調(diào)整為