【文章內(nèi)容簡介】 )。 readln(n)。 for i:=1 to n do //輸入序列的初始值 begin read(b[i,1])。 b[i,2]:=1。b[i,3]:=0。 end。 for i:=n1 downto 1 do //求最長不下降序列 begin L:=0。k:=0。 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]。 k:=j。 end。 if L0 then begin b[i,2]:=L+1。b[i,3]:=k。 end。 end。 k:=1。 for j:=1 to n do //求最長不下降序列的起始位置 if b[j,2]b[k,2] then k:=j。 writeln(39。max=39。,b[k,2])。 //輸出結(jié)果 while k0 do //輸出最長不下降序列 begin write(b[k,1]:4)。 k:=b[k,3]。 end。 writeln。 readln。 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】 攔截導(dǎo)彈 1(Noip1999) 某國為了防御敵國的導(dǎo)彈襲擊，發(fā)展出一種導(dǎo)彈攔截系統(tǒng)。但是這種攔截系統(tǒng)有一個缺陷：雖然它的第一發(fā)炮彈能夠到達任意的高度，但是以后每一發(fā)炮彈都不能高于前一發(fā)的高度。某天，雷達捕捉到敵國的導(dǎo)彈來襲，由于該系統(tǒng)還在試用階段。所以只有一套系統(tǒng)，因此有可能不能攔截所有的導(dǎo)彈。 輸入導(dǎo)彈依次飛來的高度 (雷達給出的高度不大于 30000的正整數(shù) )。計算這套系統(tǒng)最多能攔截多少導(dǎo)彈。 輸入： N顆依次飛來的導(dǎo)彈高度，（導(dǎo)彈個數(shù) =1000）。 輸出：一套系統(tǒng)最多攔截的導(dǎo)彈數(shù)，并依次打印輸出被攔截導(dǎo)彈的高度。 在本題中不僅要求輸出最優(yōu)解，而且還要求輸出最優(yōu)解的形成過程。為此，我們設(shè)置了一張記憶表 C[i]，在按從后往前方式求解的過程中，將每一個子問題的最佳決策保存起來，避免在輸出方案時重復(fù)計算。 階段 i：由右而左計算導(dǎo)彈 n‥ 導(dǎo)彈 1中可攔截的最多導(dǎo)彈數(shù)（ 1≤i≤n）； 狀態(tài) B[i]：由于每個階段中僅一個狀態(tài)，因此可通過一重循環(huán) for i := n1 downto 1 do 枚舉每個階段的狀態(tài) B[i]； 決策 k：在攔截導(dǎo)彈 i之后應(yīng)攔截哪一枚導(dǎo)彈可使得 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。 Var a,b,c: array[1..1000] of longint。 n,i,j,k,max: longint。 begin n := 0。 //初始化，讀入數(shù)據(jù) while not eoln do begin //eoln：行結(jié)束標(biāo)志 inc(n)。 read(a[n])。 b[n] := 1。 c[n] := 0。 end。 readln。 for i := n1 downto 1 do begin //枚舉每一個階段的狀態(tài)，設(shè)導(dǎo)彈 i被攔截 max := 0。 k := 0。 for j := i+1 to n do //枚舉決策，計算最佳方案中攔截的下一枚導(dǎo)彈 if (a[j] = a[i]) and (b[j] max) then begin max := b[j]。 k := j。 end。 b[i] := max+1。 c[i] := k。 //若導(dǎo)彈 i之后攔截導(dǎo)彈 k為最佳方案，則記下 end。 max := 0。 for i := 1 to n do //枚舉求出一套系統(tǒng)能攔截的最多導(dǎo)數(shù) if b[i] max then begin max := b[i]。 k := i。 end。 writeln(39。Max = 39。,b[k])。 //打印輸出結(jié)果 while k 0 do begin write(a[k]:5)。 k := c[k]。 end。 readln。 end. 【 例 5】 攔截導(dǎo)彈 2(Noip1999) 某國為了防御敵國的導(dǎo)彈襲擊，發(fā)展出一種導(dǎo)彈攔截系統(tǒng)。但是這種導(dǎo)彈攔截系統(tǒng)有一個缺陷：雖然它的第一發(fā)炮彈能夠到達任意的高度，但是以后每一發(fā)炮彈都不能高于前一發(fā)的高度。某天，雷達捕捉到敵國的導(dǎo)彈來襲。由于該系統(tǒng)還在試用階段，所以只有一套系統(tǒng)，因此有可能不能攔截所有的導(dǎo)彈。 輸入導(dǎo)彈依次飛來的高度（雷達給出的高度數(shù)據(jù)是不大于 30000的正整數(shù)），計算這套系統(tǒng)最多能攔截多少導(dǎo)彈，如果要攔截所有導(dǎo)彈最少要配備多少套這種導(dǎo)彈攔截系統(tǒng)。 樣例： INPUT OUTPUT 389 207 155 300 299 170 158 65 6（最多能攔截的導(dǎo)彈數(shù)） 2（要攔截所有導(dǎo)彈最少要配備的系統(tǒng)數(shù)） 【 算法分析 】 第一問即經(jīng)典的最長不下降子序列問題，可以用一般的 DP算法，也可以用高效算法，但這個題的數(shù)據(jù)規(guī)模好像不需要。 高效算法是這樣的：用 a[x]表示原序列中第 x個元素， b[x]表示長度為 x的不下降子序列的最后一個元素的最小值， b數(shù)組初值為無窮大。容易看出，這個數(shù)組是遞減的（當(dāng)然可能有相鄰兩個元素相等）。當(dāng)處理第 a[x]時，用二分法查找它可以連接到長度最大為多少的不下降子序列后（即與部分 b[x]比較）。假設(shè)可以連到長度最大為 y的不下降子序列后，則 b[y+1]:=min(b[y+1],a[x])。最后， b數(shù)組被賦值的元素最大下標(biāo)就是第一問的答案。由于利用了二分查找，這種算法的復(fù)雜度為 O(nlogn)，優(yōu)于一般的 O(n^2)。 第二問用貪心法即可。每顆導(dǎo)彈來襲時，使用能攔截這顆導(dǎo)彈的防御系統(tǒng)中上一次攔截導(dǎo)彈高度最低的那一套來攔截。若不存在符合這一條件的系統(tǒng)，則使用一套新系統(tǒng)。 【 參考程序 】 （順推法） program tju1004。 const max=20。 var a,b,h:array[1..max]of longint。 i,j,m,n,x,max:integer。 begin repeat inc(i)。 max:=0。 read(a[i])。 for j:=1 to i1 do //計算前 i1個導(dǎo)彈最佳攔截的方案 if a[j]=a[i] then if b[j]max then max:=b[j]。 b[i]:=max+1。 //在前 i1個導(dǎo)彈最佳方案 +1 if b[i]m then m:=b[i]。 x:=0。 for j:=1 to n do //計算由哪一套系統(tǒng)攔截導(dǎo)彈 if h[j]=a[i] then if x=0 then x:=j else if h[j]h[x] then x:=j。 if x=0 then begin inc(n)。x:=n。end。 //新增一套導(dǎo)彈攔截系統(tǒng) h[x]:=a[i]。 until seekeof。 //eof：文件結(jié)束標(biāo)志 writeln(m,39。 39。,n)。 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。試用動態(tài)規(guī)劃的最優(yōu)化原理求出 AE的最省費用。 交通圖 1 交通圖 2 如圖：求 v1到 v10的最短路徑長度及最短路徑。 【 樣例輸入 】 10 0 2 5 1 0 0 0 0 0 0 0 0 0 0 12 14 0 0 0 0 0 0 0 0 6 10 4 0 0 0 0 0 0 0 13 12 11 0 0 0 0 0 0 0 0 0 0 3 9 0 0 0 0 0 0 0 0 6 5 0 0 0 0 0 0 0 0 0 10 0 0 0 0 0 0 0 0 0 0 5 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 【 樣例輸出 】 minlong=19 1 3 5 8 10 【 算法分析 】 逆推法 設(shè) f(i)表示點 i到 v10的最短路徑長度，則 f(10)=0 f(i)=min{ a[i,x]+f(x) 當(dāng) a[i,x]0 ,ix=n} 【 參考程序 】 （逆推法） program short。 var a:array[1..100,1..100] of integer。 f,c:array[1..100] of integer。 i,j,n,x:integer。 begin assign(input,39。39。)。 assign(output,39。39。)。 reset(input)。 rewrite(output)。 readln(n)。 for i:=1 to n do //輸入各個城市之間距離 for j:=1 to n do read(a[i,j])。 for i:=1 to n do f[i]: