【正文】 for i:=n downto 1 do //按照由右而左的順序計算 c序列 begin c[i]:=1。第二行有 n個整數，用空格分隔，第 i個整數 Ti（ 130 ≤ Ti ≤ 230）是第 i位同學的身高（厘米）。 fillchar(f0,sizeof(f0),0)。 //重量進入 n序列 n[n[0]]:=total。在這種情況下，是否非得通過枚舉所有路徑方案后才能得出路徑數目，有沒有一條簡便和快效的“捷徑”呢。 如上數據，則可得下面結果： 編號 南岸 北岸 交叉數 1 1 3 2 2 2 4 2 3 3 1 2 4 4 5 1 5 5 2 3 此時， 3航線的交叉數都一樣，如果刪去的是 5線，則剩下的 4線互不相交，最多航線數為 3；但如果刪去的是 3，則還要刪去第 5線才符合要求，此時的最多航線數為 2，不是最優(yōu)解。close(output)。 f[i,1]:=L+w[i]。)。設計一個挖地雷的方案，使他能挖到最多的地雷。 for i:=1 to n do f[i]:=maxint。試用動態(tài)規(guī)劃的最優(yōu)化原理求出 AE的最省費用。 max:=0。 輸入導彈依次飛來的高度（雷達給出的高度數據是不大于 30000的正整數），計算這套系統最多能攔截多少導彈，如果要攔截所有導彈最少要配備多少套這種導彈攔截系統。 //若導彈 i之后攔截導彈 k為最佳方案，則記下 end。 Var a,b,c: array[1..1000] of longint。 //輸出結果 while k0 do //輸出最長不下降序列 begin write(b[k,1]:4)。b[i,3]:=0。 end。b(I,3)表示從 I位置開始最長不下降序列的下一個位置，若 b[I,3]=0則表示后面沒有連接項。,max)。 max: word。 //輸出數塔最大值 y:=1。 【 參考程序 】 program ex14_2_1。在用動態(tài)規(guī)劃考慮數塔問題時可以自頂向下的分析，自底向上的計算。 d[4,3,1] := 3。 i,j,k,min : integer。所謂無后效性原則，指的是這樣一種性質：某階段的狀態(tài)一旦確定，則此后過程的演變不再受此前各狀態(tài)及決策的影響。如例題 1中， C3是一個狀態(tài)變量。 第一節(jié) 動態(tài)規(guī)劃的基本模型 ? 多階段決策過程的最優(yōu)化問題 在現實生活中，有一類活動的過程，由于它的特殊性，可將過程分成若干個互相聯系的階段，在它的每一階段都需要作出決策，從而使整個過程達到最好的活動效果。 下圖給出了一個地圖，地圖中的每個頂點代表一個城市，兩個城市間的一條連線代表道路，連線上的數值代表道路的長度。如例題 1中， F3（ C3）就是一個決策變量。這些決策形成一個決策序列，同時確定了完成整個過程的一條活動路線，通常是求最優(yōu)活動路線。 d[2,1,2] := 6。 readln。實際求解時應掌握其編程的一般規(guī)律，通常需要哪幾個關鍵數組來存儲變化過程這一點非常重要。)。 //下一行的列數 end。 fillchar(a,sizeof(a),0)。例中13， 16， 18， 19， 21， 22， 63就是一個長度為 7的不下降序列，同時也有 7 ， 9，16， 18， 19， 21， 22， 63長度為 8的不下降序列。 最后本題經過計算，其數據存儲表如下： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 13 7 9 16 38 24 37 18 44 19 21 22 63 15 7 8 7 6 3 4 3 5 2 4 3 2 1 1 4 3 4 8 9 7 9 10 13 11 12 13 0 0 初始化 : for i:=1 to n do begin read(b[i,1])。 k:=b[k,3]。 k:=j。 end. 程序運行結果： 輸入： 14 13 7 9 16 38 24 37 18 44 19 21 22 63 15 輸出： max=8 7 9 16 18 19 21 22 63 【 例 4】 攔截導彈 1(Noip1999) 某國為了防御敵國的導彈襲擊，發(fā)展出一種導彈攔截系統。 b[n] := 1。 writeln(39。假設可以連到長度最大為 y的不下降子序列后，則 b[y+1]:=min(b[y+1],a[x])。 x:=0。 i,j,n,x:integer。minlong=39。 【 參考程序 】 program Mine。 for i:=1 to n do //輸入每個地窖中的地雷數 read(w[i])。 max:=f[k,1]。 【 輸入格式 】 輸入文件 ():包括了若干組數據，每組數據格式如下： 第一行兩個由空格分隔的整數 x， y， 10〈 =x〈 =6000， 10〈 =y〈 =100。 Si為航線的終點坐標值。由于棋盤規(guī)模的上限為 50*50，可能導致路徑數目大得驚人，因此不妨設 map數組的元素類型為 extended。 要求從 n個物品中，任取若干個裝入箱內，使箱子的剩余空間為最小。 //若物品 i裝入箱子后的體積正好為 j,則物品 i裝入箱子 f0:=f1。設 a 為身高序列，其中 a[i]為同學 i的身高； b 為由左而右身高遞增的人數序列，其中 b[i]為同學 1‥ 同學 i間（包括同學 i）身高滿足遞增順序的最多人數。 writeln(nmax+1)。 //讀每個學生的身高 fillchar(b,sizeof(b),0)。 end。初始時， f[0， 0]=true（ 1≤i≤n，box[i]≤j≤v）。 //輸入６種砝碼的個數 n[0]:=1。例如： (N=10， M=10)， (1， 5)(起點 )， (3，5)(終點 )。 【 輸入輸出樣例 】 30 4 5 4 5 2 4 5 2 1 3 3 1 3 【 算法分析 】 我們將每對友好城市看成一條線段，則這道題的描述化為：有 N條線段，問最少去掉多少條線，可以使剩下的線段互不交叉？ 第一，以北岸為線的起點而南岸為線的終點；先將所有的線按照起點坐標值從小到大排序，按照每條線的終點坐標計算交叉數：求線 I的交叉數 J[I]，則檢查所有 1..I1條線，若線 J( 1= J I)的終點值大于線 I的終點值，則線 I與線 J相交。 k:=f[k,2]。 //從后 F(n)往前逐個找出所有的 F(i) for i:=n1 downto 1 do begin L:=0。39。 close(input)。)。 until seekeof。 【 參考程序 】 （順推法） program tju1004。 readln。 for j := i+1 to n do //枚舉決策，計算最佳方案中攔截的下一枚導彈 if (a[j] = a[i]) and (b[j] max) then begin max := b[j]。 輸入： N顆依次飛來的導彈高度，（導彈個數 =1000）。 k:=1。input n:39。 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]。 3 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]。在本題中僅要求輸出最優(yōu)解，為此我們設置了數組 A[i,j]保存三角形數塔， B[i,j]保存狀態(tài)值，按從上往下方式進行求解。 a[x,y,3]:=0 end else begin a[x,y,2]:=a[x,y,2]+a[x+1,y+1,2]。 貪心法問題所在：眼光短淺。而遞推法在處理判定性問題和計數問題方面也是一把利器。 d[3,2,1] := 5。所以如果確定了決策，狀態(tài)轉移方程也就可以寫出。 一般來說，能夠采用動態(tài)規(guī)劃方法求解的問題，必須滿足最優(yōu)化原理和無后效性原則： 動態(tài)規(guī)劃的最優(yōu)化原理。 ? 動態(tài)規(guī)劃的基本概念和基本模型構成 現在我們來介紹動態(tài)規(guī)劃的基本概念。第九章 動態(tài)規(guī)劃 第一節(jié) 動態(tài)規(guī)劃的基本模型 第二節(jié) 動態(tài)規(guī)劃與遞推 第三節(jié) 歷屆 NOIP動態(tài)規(guī)劃試題 第四節(jié) 背包問題 第五節(jié) 動態(tài)規(guī)劃應用舉例 動態(tài)規(guī)劃程序設計是對解最優(yōu)化問題的一種途徑、一種方法，而不是一種特殊算法。 在上例的多階段決策問題中，各個階段采取的決策，一般來說是與階段有關的，決策依賴于當前狀態(tài)，又隨即引起狀態(tài)的轉移，一個決策序列就是在變化的狀態(tài)中產生出來的，故有“動態(tài)”的含義，我們稱這種解決多階段決策最優(yōu)化的過程為動態(tài)規(guī)劃程序設計方法。 ? 最優(yōu)化原理與無后效性 上面已經介紹了動態(tài)規(guī)劃模型的基本組成，現在需要解決的問題是：什么樣的“多階段決策問題”才可以采用動態(tài)規(guī)劃的方法求解。 確定決策并寫出狀態(tài)轉移方程 因為決策和狀態(tài)轉移有著天然的聯系，狀態(tài)轉移就是根據上一階段的狀態(tài)和決策來導出本階段的狀態(tài)。 d[3,1,2] := 6。我們在競賽中碰到的大多是最優(yōu)化問題，而動態(tài)規(guī)劃正是解決最優(yōu)化問題的有力武器，因此動態(tài)規(guī)劃在競賽中的地位日益提高。 【 解法一 】 （逆推法） 【 算法分析 】 ① 貪心法往往得不到最優(yōu)解：本題若采用貪心法則： 1311121413，其和為 63,但存在另一條路： 138261524，其和為 86。 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]。因此本題是一個典型的多階段決策最優(yōu)化問題。 b[1,1] := a[1,1]。 ②若 b(n1)b(n)則存在長度為 1的不下降序列 b(n1)或 b(n)。k:=0。 begin writeln(39。 end。計算這套系統最多能攔截多少導彈。 k := 0。 end。若不存在符合這一條件的系統，則使用一套新系統。 //新增一套導彈攔截系統 h[x]:=a[i]。39。 end。 begin assign(input,39。 f[n,1]:=w[n]。,k)。 【 輸出格式 】 輸出文件 ()：要在連續(xù)的若干行里給出每一組數據在安全條件下能夠開通的最大航線數目。即圖所示： 當 N， M 給出之后，同時給出馬起始的位置和終點的位置，試找出從起點到終點的所有路徑的數目。 fo