【正文】 】 program Mine。設(shè) W(i)為第 i個地窖所藏有的地雷數(shù)， A（ i,j）表示第 i個地窖與第 j個地窖之間是否有通路， F(i)為從第 i個地窖開始最多可以挖出的地雷數(shù)，則有如下遞歸式： F(i)=MAX { W(i)+ F(j) } (ij=n , A(i,j)=true) 邊界： F(n)=W(n) 于是就可以通過遞推的方法，從后 F(n)往前逐個找出所有的 F(i)，再從中找一個最大的即為問題 2的解。 【 輸入格式 】 N //地窖的個數(shù) W1， W2， ……WN // 每個地窖中的地雷數(shù) X1， Y1 //表示從 X1可到 Y1 X2， Y2 …… 0， 0 //表示輸入結(jié)束 【 輸出格式 】 K1——K2——…… ——Kv //挖地雷的順序 MAX //最多挖出的地雷數(shù) 【 輸入樣例 】 6 5 10 20 5 4 5 1 2 1 4 2 4 3 4 4 5 4 6 5 6 0 0 【 輸出樣例 】 3456 34 【 算法分析 】 本題是一個經(jīng)典的動態(tài)規(guī)劃問題。某人可以從任一處開始挖地雷，然后沿著指出的連接往下挖（僅能選擇一條路徑），當無連接時挖地雷工作結(jié)束。 end. 【 例 7】 挖地雷（ ） 【 問題描述 】 在一個地圖上有 N個地窖（ N=200） ,每個地窖中埋有一定數(shù)量的地雷。 close(input)。 x:=c[x]。 //輸出最短路徑的值 x:=1。minlong=39。c[i]:=x end。 //初始化 ，默認每一個城市到達終點都是 maxint f[n]:=0。 for i:=1 to n do //輸入各個城市之間距離 for j:=1 to n do read(a[i,j])。 rewrite(output)。)。 assign(output,39。39。 i,j,n,x:integer。 var a:array[1..100,1..100] of integer。 交通圖 1 交通圖 2 如圖：求 v1到 v10的最短路徑長度及最短路徑。 end. 經(jīng)過計算，其數(shù)據(jù)存儲表如下 I I=1 I=2 I=3 I=4 I=5 I=6 I=7 I=8 A[I] 389 207 155 300 299 170 158 65 B[I] 1 2 3 2 3 4 5 6 N值 1 2 H[1] 389 207 155 65 H[2] 300 299 170 158 【 例 6】 下圖表示城市之間的交通路網(wǎng)，線段上的數(shù)字表示費用，單向通行由 AE。 39。 until seekeof。end。 if x=0 then begin inc(n)。 x:=0。 b[i]:=max+1。 read(a[i])。 begin repeat inc(i)。 var a,b,h:array[1..max]of longint。 【 參考程序 】 （順推法） program tju1004。每顆導彈來襲時，使用能攔截這顆導彈的防御系統(tǒng)中上一次攔截導彈高度最低的那一套來攔截。由于利用了二分查找，這種算法的復雜度為 O(nlogn)，優(yōu)于一般的 O(n^2)。假設(shè)可以連到長度最大為 y的不下降子序列后，則 b[y+1]:=min(b[y+1],a[x])。容易看出，這個數(shù)組是遞減的（當然可能有相鄰兩個元素相等）。 樣例： INPUT OUTPUT 389 207 155 300 299 170 158 65 6（最多能攔截的導彈數(shù)） 2（要攔截所有導彈最少要配備的系統(tǒng)數(shù)） 【 算法分析 】 第一問即經(jīng)典的最長不下降子序列問題，可以用一般的 DP算法，也可以用高效算法，但這個題的數(shù)據(jù)規(guī)模好像不需要。由于該系統(tǒng)還在試用階段，所以只有一套系統(tǒng)，因此有可能不能攔截所有的導彈。但是這種導彈攔截系統(tǒng)有一個缺陷：雖然它的第一發(fā)炮彈能夠到達任意的高度，但是以后每一發(fā)炮彈都不能高于前一發(fā)的高度。 readln。 k := c[k]。,b[k])。 writeln(39。 k := i。 max := 0。 c[i] := k。 end。 for j := i+1 to n do //枚舉決策，計算最佳方案中攔截的下一枚導彈 if (a[j] = a[i]) and (b[j] max) then begin max := b[j]。 for i := n1 downto 1 do begin //枚舉每一個階段的狀態(tài)，設(shè)導彈 i被攔截 max := 0。 end。 b[n] := 1。 //初始化，讀入數(shù)據(jù) while not eoln do begin //eoln：行結(jié)束標志 inc(n)。 n,i,j,k,max: longint。 階段 i：由右而左計算導彈 n‥ 導彈 1中可攔截的最多導彈數(shù)（ 1≤i≤n）； 狀態(tài) B[i]：由于每個階段中僅一個狀態(tài)，因此可通過一重循環(huán) for i := n1 downto 1 do 枚舉每個階段的狀態(tài) B[i]； 決策 k：在攔截導彈 i之后應(yīng)攔截哪一枚導彈可使得 B[i]最大（ i+1≤k≤n）， 1 2 3 4 5 6 7 8 9 10 11 12 13 14 I 13 7 9 16 38 24 37 18 44 19 21 22 63 15 A[I] //高度 2 1 1 2 4 3 3 2 3 2 2 2 2 1 B[I] //可攔截數(shù) 2 0 0 14 6 8 8 14 10 14 14 14 14 0 C[I] //再攔截 【 參考程序 】 （逆推法） program ex14_4_1。 在本題中不僅要求輸出最優(yōu)解，而且還要求輸出最優(yōu)解的形成過程。 輸入： N顆依次飛來的導彈高度，（導彈個數(shù) =1000）。 輸入導彈依次飛來的高度 (雷達給出的高度不大于 30000的正整數(shù) )。某天，雷達捕捉到敵國的導彈來襲，由于該系統(tǒng)還在試用階段。 end. 程序運行結(jié)果： 輸入： 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ā)展出一種導彈攔截系統(tǒng)。 writeln。 k:=b[k,3]。,b[k,2])。 writeln(39。 k:=1。 end。 if L0 then begin b[i,2]:=L+1。 k:=j。k:=0。 end。 b[i,2]:=1。 readln(n)。input n:39。 b:array[1..100,1..3]of integer。 【 參考程序 】 program ex14_3。 k:=b[k,3]。 for j:=1 to n do if b[j,2]b[k,2] then k:=j。 end。 b[i,3]:=k。 end。 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 i:=n1 downto 1 do begin L:=0。b[i,3]:=0。 最后本題經(jīng)過計算，其數(shù)據(jù)存儲表如下： 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])。 ② 若 L0，則 b[I,2]:=L+1。 ㈣ 求解過程： ①從倒數(shù)第二項開始計算，后面僅有 1項，比較一次，因 6315，不符合要求，長度仍為 1。b(I,2)表示從 I位置到達 N的最長不下降序列長度 3 ㈢數(shù)據(jù)結(jié)構(gòu)： 為算法上的需要，定義一個整數(shù)類型二維數(shù)組 b(N,3) 1 3若從 b(n1)開始查找，則存在下面的兩種可能性： ①若 b(n1)b(n)則存在長度為 2的不下降序列 b(n1)， b(n)。 1例中13， 16， 18， 19， 21， 22， 63就是一個長度為 7的不下降序列，同時也有 7 ， 9，16， 18， 19， 21， 22， 63長度為 8的不下降序列。程序要求，當原數(shù)列出之后，求出最長的不下降序列。 //輸出數(shù)塔最大值 readln。Max = 39。 for i := 1 to n do if b[n,i] max then max := b[n,i]。 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]。 b := a。 readln。 fillchar(a,sizeof(a),0)。)。 begin write(39。 i,j,n : integer。 【 參考程序 】 program ex14_2_2。在本題中僅要求輸出最優(yōu)解，為此我們設(shè)置了數(shù)組 A[i,j]保存三角形數(shù)塔， B[i,j]保存狀態(tài)值，按從上往下方式進行求解。如果得到一條由頂?shù)降椎哪程幍囊粭l最佳路徑，那么對于該路徑上的每一個中間點來說，由頂點至該中間點的路徑所