【正文】 x:=0。 for j:=1 to i1 do //計算前 i1個導(dǎo)彈最佳攔截的方案 if a[j]=a[i] then if b[j]max then max:=b[j]。 //在前 i1個導(dǎo)彈最佳方案 +1 if b[i]m then m:=b[i]。 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。x:=n。 //新增一套導(dǎo)彈攔截系統(tǒng) h[x]:=a[i]。 //eof：文件結(jié)束標(biāo)志 writeln(m,39。,n)。試用動態(tài)規(guī)劃的最優(yōu)化原理求出 AE的最省費(fèi)用。 【 樣例輸入 】 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)表示點(diǎn) i到 v10的最短路徑長度，則 f(10)=0 f(i)=min{ a[i,x]+f(x) 當(dāng) a[i,x]0 ,ix=n} 【 參考程序 】 （逆推法） program short。 f,c:array[1..100] of integer。 begin assign(input,39。)。39。 reset(input)。 readln(n)。 for i:=1 to n do f[i]:=maxint。 for i:= n1 downto 1 do //從終點(diǎn)往前逆推，計算最短路徑 for x:= i+1 to n do //若 f[x]=maxint表示城市 x到終點(diǎn)城市不通 if (a[i,x]0) and (f[x]maxint) and (f[i]a[i,x]+f[x]) //a[i,x]0表示城市 i和城市 x通路 then begin f[i]:=a[i,x]+f[x]。 //城市 i到終點(diǎn)最短路徑的值 writeln(39。,f[1])。 while x0 do //輸出路過的各個城市 begin write(x:5)。 end。close(output)。同時，給出地窖之間的連接路徑，并規(guī)定路徑都是單向的。設(shè)計一個挖地雷的方案，使他能挖到最多的地雷。很明顯，題目規(guī)定所有路徑都是單向的，所以滿足無后效性原則和最優(yōu)化原理。對于具體所走的路徑（問題 1），可以通過一個向后的鏈接來實現(xiàn)。 var f:array[1..200,1..2] of longint。 w:array[1..200] of longint。 begin assign(input,39。)。 assign(output,39。)。 fillchar(a,sizeof(a),false)。 readln(n)。 readln。 //表示從 X可到 Y if (x0) and (y0) then a[x,y]:=true。 f[n,1]:=w[n]。 k:=0。 k:=j。 f[i,1]:=L+w[i]。 //k地窖是 i地窖最優(yōu)路徑 end。 for j:=2 to n do //計算最多挖出的地雷數(shù) if f[j,1]f[k,1] then k:=j。write(k)。 while k0 do //輸出挖地雷的順序 begin write(39。,k)。 end。 writeln(max)。close(output)。每一對友好城市都希望有一條航線來往，于是他們向政府提出了申請。興建哪些航線以使在安全條件下有最多航線可以被開通。 x表示河的長度而 y表示寬。接下來的 N行每行有兩個由空格分隔的正數(shù) C， D（ C、 D〈 =x〉 ， 描述每一對友好城市與河起點(diǎn)的距離， C表示北岸城市的距離而 D表示南岸城市的距離。 【 輸出格式 】 輸出文件 ()：要在連續(xù)的若干行里給出每一組數(shù)據(jù)在安全條件下能夠開通的最大航線數(shù)目。 J[I]與 J[J]同時加 1。 第二，將 J數(shù)組從大到小排序，每刪除一條線，則將與之相交的線的 J值減 1，重復(fù)這個過程，直到所有 J值都為 0。 如上數(shù)據(jù)，則可得下面結(jié)果： 編號 南岸 北岸 交叉數(shù) 1 1 3 2 2 2 4 2 3 3 1 2 4 4 5 1 5 5 2 3 此時， 3航線的交叉數(shù)都一樣，如果刪去的是 5線，則剩下的 4線互不相交，最多航線數(shù)為 3；但如果刪去的是 3，則還要刪去第 5線才符合要求，此時的最多航線數(shù)為 2，不是最優(yōu)解。因此，求所有線中最多能有多少條線不相交，實際上是從終點(diǎn)坐標(biāo)值數(shù)列中求一個最長不下降序列。 求最長不下降序列的規(guī)劃方程如下： L(Si)=max{L(Sj)}+1； 1 = j i且 Sj Si。 從以上分析過程可以得出：當(dāng)我們拿到一道題時，不要急于求解，而應(yīng)先將題目的表面現(xiàn)象一層層象剝竹筍一樣去掉，只留下最實質(zhì)的內(nèi)容。 第三節(jié) 歷屆 NOIP動態(tài)規(guī)劃試題 【 例題 1】 騎士游歷問題 設(shè)有一個 n*m的棋盤 (2≤n≤50， 2≤m≤50)，如圖 1。即圖所示： 當(dāng) N， M 給出之后，同時給出馬起始的位置和終點(diǎn)的位置，試找出從起點(diǎn)到終點(diǎn)的所有路徑的數(shù)目。應(yīng)輸出 2(即由 (1， 5)到 (3， 5)共有 2條路徑，如圖： 【 輸入格式 】 n， m， x1， y1， x2， y2(分別表示 n， m，起點(diǎn)坐標(biāo)，終點(diǎn)坐標(biāo) ) 【 輸出格式 】 路徑數(shù)目 (若不存在從起點(diǎn)到終點(diǎn)的路徑，輸出 0) 【 算法分析 】 使用回溯法同樣可以計算路徑數(shù)目。但問題是搜索效率太低，根本不可能在較短的時間內(nèi)出解。在這種情況下，是否非得通過枚舉所有路徑方案后才能得出路徑數(shù)目，有沒有一條簡便和快效的“捷徑”呢。位于（ x， y）左方且可達(dá)（ x， y）的跳馬位置集合都是（ x， y）的子問題，起點(diǎn)至（ x， y）的路徑數(shù)實際上等于起點(diǎn)至這些位置集的路徑數(shù)之和（圖 4）。設(shè)狀態(tài)轉(zhuǎn)移方程 map，其中map[i， j]為起點(diǎn)（ x1， y1）至（ i， j）的路徑數(shù)目。初始時，除 map[x1， y1]=1外其余為０。在分析第 i種砝碼的放置方案時，依次在現(xiàn)有的不同重量的基礎(chǔ)上，放 1塊、 2塊 ……a[i] 塊，產(chǎn)生新的不同重量。 for i:=1 to 6 do read(a[i])。n[1]:=0。 //產(chǎn)生重量 if not h[total] then //若該重量未產(chǎn)生過，則設(shè)訪問標(biāo)志 begin h[total]:=true。 //重量進(jìn)入 n序列 n[n[0]]:=total。 end。 //輸出不同重量的個數(shù) 【 例題 3】 裝箱問題 【 問題描述 】 有一個箱子容量為 v（正整數(shù)， 0≤v≤20210），同時有 n個物品（ 0n≤30），每個物品有一個體積（正整數(shù)）。 【 輸入格式 】 箱子的容量 v 物品數(shù) n 接下來 n行，分別表示這 n個物品的體積 【 輸出格式 】 箱子剩余空間 【 輸入輸出樣例 】 輸入： 24 6 8 3 12 7 9 7 輸出： 0 【 算法分析 】 使用 動態(tài)程序設(shè)計方法計算箱子的最小剩余空間，如果按照物品序號依次考慮裝箱順序的話，則問題具有明顯的階段特征。但如果將裝箱的體積作為狀態(tài)的話，則階段間的狀態(tài)轉(zhuǎn)移關(guān)系順其自然，可使得最優(yōu)化問題變?yōu)榕卸ㄐ詥栴}。顯然 f[i， j]=f[i1， jbox[i]]，即物品 i裝入箱子后的體積正好為 j的前提是 f[i1， jbox[i]]=true。 由 f[i， j]=f[i1， jbox[i]]可以看出，當(dāng)前階段的狀態(tài)轉(zhuǎn)移方程僅與上一階段的狀態(tài)轉(zhuǎn)移方程相關(guān)。我們按照下述方法計算狀態(tài)轉(zhuǎn)移方程 f1： readln(v,n)。 fillchar(f0,sizeof(f0),0)。 for i:=1 to n do //階段 i:按照物品數(shù)遞增的順序考慮裝箱情況 begin f1:=f0。 for j:=x[i] to v do //狀態(tài) j：枚舉所有可能的裝箱體積 if f0[jx[i]] then f1[j]:=true。 //記下當(dāng)前裝箱情況 end。再借用動態(tài)程序設(shè)計的思想，計算裝箱的最大體積 。 halt。 【 例題 4】 合唱隊形 【 問題描述 】 N位同學(xué)站成一排，音樂老師要請其中的 (NK)位同學(xué)出列，使得剩下的 K位同學(xué)排成合唱隊形。 你的任務(wù)是，已知所有 N位同學(xué)的身高，計算最少需要幾位同學(xué)出列，可以使得剩下的同學(xué)排成合唱隊形。第二行有 n個整數(shù)，用空格分隔，第 i個整數(shù) Ti（ 130 ≤ Ti ≤ 230）是第 i位同學(xué)的身高（厘米）。 【 樣例輸入 】 8 186 186 150 200 160 130 197 220 【 樣例輸出 】 4 【 數(shù)據(jù)規(guī)模 】 對于 50%的數(shù)據(jù)，保證有 n ≤ 20；對于全部的數(shù)據(jù)，保證有 n≤100。如何分別在這兩個數(shù)列中尋求遞增的、未必連續(xù)的最長子序列，就成為問題的關(guān)鍵。顯然 b[i]={b[j]|同學(xué) j的身高 同學(xué) i的身高 }+1； c為由右而左身高遞增的人數(shù)序列，其中 c[i]為同學(xué) n‥ 同學(xué) i間（包括同學(xué) i）身高滿足遞增順序的最多人數(shù)。 顯然，合唱隊的人數(shù)為 (公式中同學(xué) i被重復(fù)計算，因此減 1)， n減去合唱隊人數(shù)即為解。 //讀學(xué)生數(shù) for i:=1 to n do read(a[i])。fillchar(c,sizeof(c),0)。 for j:=1 to i1 do if (a[i]a[j])and(b[j]+1b[i]) then b[i]:=b[j]+1。 for i:=n downto 1 do //按照由右而左的順序計算 c序列 begin c[i]:=1。 end。 //計算合唱隊的人數(shù) max（其中 1人被重復(fù)計算 for i:=1 to n do if b[i]+c[i]max then max:=b[i]+c[i]。 //輸出出列人數(shù) 這個算法的時間復(fù)雜度為 O(n2)，在 1秒時限內(nèi)可解決 n≤100范圍內(nèi)