1、動態(tài)規(guī)劃 動態(tài)規(guī)劃程序設(shè)計是對解最優(yōu)化問題的一種途徑、一種方法，而不是一種特殊算法。不象前面所述的那些搜索或數(shù)值計算那樣，具有一個標(biāo)準(zhǔn)的數(shù)學(xué)表達式和明確清晰的解題方法。動態(tài)規(guī)劃程序設(shè)計往往是針對一種最優(yōu)化問題，由于各種問題的性質(zhì)不同，確定最優(yōu)解的條件也互不相同，因而動態(tài)規(guī)劃的設(shè)計方法對不同的問題，有各具特色的解題方法，而不存在一種萬能的動態(tài)規(guī)劃算法，可以解決各類最優(yōu)化問題。因此讀者在學(xué)習(xí)時，除了要對基本概念和方法正確理解外，必須具體問題具體分析處理，以豐富的想象力去建立模型，用創(chuàng)造性的技巧去求解。我們也可以通過對若干有代表性的問題的動態(tài)規(guī)劃算法進行分析、討論，逐漸學(xué)會并掌握這一設(shè)計方法。動態(tài)規(guī)

2、劃的基本模型動態(tài)規(guī)劃的基本模型w多階段決策過程的最優(yōu)化問題多階段決策過程的最優(yōu)化問題 在現(xiàn)實生活中，有一類活動的過程，由于它的特殊性，可將過程分成若干個互相聯(lián)系的階段，在它的每一階段都需要作出決策，從而使整個過程達到最好的活動效果。當(dāng)然，各個階段決策的選取不是任意確定的，它依賴于當(dāng)前面臨的狀態(tài)，又影響以后的發(fā)展，當(dāng)各個階段決策確定后，就組成一個決策序列，因而也就確定了整個過程的一條活動路線，這種把一個問題看作是一個前后關(guān)聯(lián)具有鏈狀結(jié)構(gòu)的多階段過程就稱為多階段決策過程，這種問題就稱為多階段決策問題。如下圖所示： 多階段決策過程，是指這樣的一類特殊的活動過程，問題可以按時間順序分解成若干相互聯(lián)系的

3、階段，在每一個階段都要做出決策，全部過程的決策是一個決策序列。要使整個活動的總體效果達到最優(yōu)的問題，稱為多階段決策問題?！纠纠?】最短路徑問題。最短路徑問題。下圖給出了一個地圖，地圖中的每個頂點代表一個城市，兩個城市間的一條連線代表道路，連線上的數(shù)值代表道路的長度?，F(xiàn)在想從城市A到達城市E，怎樣走路程最短？最短路程的長度是多少？【算法分析】【算法分析】 把A到E的全過程分成四個階段，用K表示階段變量，第1階段有一個初始狀態(tài)A，有兩條可供選擇的支路A-B1、A-B2；第2階段有兩個初始狀態(tài)B1、B2，B1有三條可供選擇的支路，B2有兩條可供選擇的支路。用DK（XI，X+1J）表示在第K階段由初

4、始狀態(tài)XI到下階段的初始狀態(tài)X+1J的路徑距離，F(xiàn)K（XI）表示從第K階段的XI到終點E的最短距離，利用倒推的方法，求解A到E的最短距離。 具體計算過程如下：S1： K = 4 有 F4（D1）= 3， F4（D2）= 4， F4（D3）= 3；S2： K = 3 有 F3（C1）= MIN D3（C1，D1）+ F4（D1），D3（C1，D2）+ F4（D2） = MIN 5+3，6+4 = 8 F3（C2）= D3（C2，D1）+ F4（D1）= 5+3 = 8 F3（C3）= D3（C3，D3）+ F4（D3）= 8+3 = 11 F3（C4）= D3（C4，D3）+ F4（D3）= 3

5、+3 = 6S3： K = 2 有 F2（B1）= MIN D2（B1，C1）+ F3（C1），D2（B1，C2）+ F3（C2）， D2（B1，C3）+ F3(C3) = MIN 1+8,6+8,3+11 = 9 F2（B2）= MIN D2（B2，C2）+ F3（C2），D2（B2，C4）+ F3（C4） = MIN 8+8，4+6 = 10S4： K = 1 有 F1（A）= MIN D1（A，B1）+ F2（B1），D1（A，B2）+ F2（B2） = MIN 5+9，3+10 = 13 因此由A點到E點的全過程最短路徑為AB2C4D3E；最短路程長度為13。 從以上過程可以看出，每個

6、階段中，都求出本階段的各個初始狀態(tài)到終點E的最短距離，當(dāng)逆序倒推到過程起點A時，便得到了全過程的最短路徑和最短距離。 在上例的多階段決策問題中，各個階段采取的決策，一般來說是與階段有關(guān)的，決策依賴于當(dāng)前狀態(tài)，又隨即引起狀態(tài)的轉(zhuǎn)移，一個決策序列就是在變化的狀態(tài)中產(chǎn)生出來的，故有“動態(tài)”的含義，我們稱這種解決多階段決策最優(yōu)化的過程為動態(tài)規(guī)劃程序設(shè)計方法?！纠纠?】對應(yīng)的Pascal程序如下：var d : array1.4,1.4,1.4 of integer; f : array1.5,1.4 of integer; i,j,k : integer;begin fillchar(d,sizeo

7、f(d),0); d1,1,1 := 5; d1,1,2 := 3; d2,1,1 := 1; d2,1,2 := 6; d2,1,3 := 3; d2,2,2 := 8; d2,2,4 := 4; d3,1,1 := 5; d3,1,2 := 6; d3,2,1 := 5; d3,3,3 := 8; d3,4,3 := 3; d4,1,1 := 3; d4,2,1 := 4; d4,3,1 := 3; for i:=1 to 5 do for j:=1 to 4 do f(i,j):=255; f5,1 := 0; for i := 4 downto 1 do for j := 1 to 4

8、 do for k := 1 to 4 do if di,j,k 0 then if fi,j di,j,k+fi+1,k then fi,j := di,j,k+fi+1,k; writeln(f1,1); readln;end.w上面已經(jīng)介紹了動態(tài)規(guī)劃模型的基本組成，現(xiàn)在需要解決的問題是：什么樣的“多階段決策問題”才可以采用動態(tài)規(guī)劃的方法求解。w 一般來說，能夠采用動態(tài)規(guī)劃方法求解的問題，必須滿足最優(yōu)化原理和無后效性原則：w 1、動態(tài)規(guī)劃的最優(yōu)子結(jié)構(gòu)原理。作為整個過程的最優(yōu)策略具有：無論過去的狀態(tài)和決策如何，對前面的決策所形成的狀態(tài)而言，余下的諸決策必須構(gòu)成最優(yōu)策略的性質(zhì)。也可以通俗地理解

9、為子問題的局部最優(yōu)將導(dǎo)致整個問題的全局最優(yōu)，即問題具有最優(yōu)子結(jié)構(gòu)的性質(zhì)，也就是說一個問題的最優(yōu)解只取決于其子問題的最優(yōu)解，而非最優(yōu)解對問題的求解沒有影響。在例題1最短路徑問題中，A到E的最優(yōu)路徑上的任一點到終點E的路徑，也必然是該點到終點E的一條最優(yōu)路徑，即整體優(yōu)化可以分解為若干個局部優(yōu)化。最優(yōu)子結(jié)構(gòu)原理最優(yōu)子結(jié)構(gòu)原理 無后效性無后效性 2、動態(tài)規(guī)劃的無后效性原則。所謂無后效性原則，指的是這樣一種性質(zhì)：某階段的狀態(tài)一旦確定，則此后過程的演變不再受此前各狀態(tài)及決策的影響。也就是說，“未來與過去無關(guān)”，當(dāng)前的狀態(tài)是此前歷史的一個完整的總結(jié)，此前的歷史只能通過當(dāng)前的狀態(tài)去影響過程未來的演變。在例題1

10、最短路徑問題中，問題被劃分成各個階段之后，階段K中的狀態(tài)只能由階段K+1中的狀態(tài)通過狀態(tài)轉(zhuǎn)移方程得來，與其它狀態(tài)沒有關(guān)系，特別與未發(fā)生的狀態(tài)沒有關(guān)系，例如從Ci到E的最短路徑，只與Ci的位置有關(guān)，它是由Di中的狀態(tài)通過狀態(tài)轉(zhuǎn)移方程得來，與E狀態(tài)，特別是A到Ci的路徑選擇無關(guān)，這就是無后效性。 由此可見，對于不能劃分階段的問題，不能運用動態(tài)規(guī)劃來解；對于能劃分階段，但不符合最優(yōu)化原理的，也不能用動態(tài)規(guī)劃來解；既能劃分階段，又符合最優(yōu)化原理的，但不具備無后效性原則，還是不能用動態(tài)規(guī)劃來解；誤用動態(tài)規(guī)劃程序設(shè)計方法求解會導(dǎo)致錯誤的結(jié)果。mod 4 最優(yōu)路徑問題 在圖中找出從第A點到第D點的一條路徑，

11、要求路徑長度mod 4的余數(shù)最小。w動態(tài)規(guī)劃的基本概念和基本模型構(gòu)成動態(tài)規(guī)劃的基本概念和基本模型構(gòu)成 現(xiàn)在我們來介紹動態(tài)規(guī)劃的基本概念。1. 階段和階段變量： 用動態(tài)規(guī)劃求解一個問題時，需要將問題的全過程恰當(dāng)?shù)胤殖扇舾蓚€相互聯(lián)系的階段，以便按一定的次序去求解。描述階段的變量稱為階段變量，通常用K表示，階段的劃分一般是根據(jù)時間和空間的自然特征來劃分，同時階段的劃分要便于把問題轉(zhuǎn)化成多階段決策過程，如例題1中，可將其劃分成4個階段，即K = 1，2，3，4。2. 狀態(tài)和狀態(tài)變量： 某一階段的出發(fā)位置稱為狀態(tài)，通常一個階段包含若干狀態(tài)。一般地，狀態(tài)可由變量來描述，用來描述狀態(tài)的變量稱為狀態(tài)變量。如例

12、題1中，C3是一個狀態(tài)變量。3. 決策、決策變量和決策允許集合： 在對問題的處理中作出的每種選擇性的行動就是決策。即從該階段的每一個狀態(tài)出發(fā)，通過一次選擇性的行動轉(zhuǎn)移至下一階段的相應(yīng)狀態(tài)。一個實際問題可能要有多次決策和多個決策點，在每一個階段的每一個狀態(tài)中都需要有一次決策，決策也可以用變量來描述，稱這種變量為決策變量。在實際問題中，決策變量的取值往往限制在某一個范圍之內(nèi)，此范圍稱為允許決策集合。如例題1中，F(xiàn)3（C3）就是一個決策變量。4策略和最優(yōu)策略： 所有階段依次排列構(gòu)成問題的全過程。全過程中各階段決策變量所組成的有序總體稱為策略。在實際問題中，從決策允許集合中找出最優(yōu)效果的策略成為最優(yōu)策

13、略。5. 狀態(tài)轉(zhuǎn)移方程 前一階段的終點就是后一階段的起點，對前一階段的狀態(tài)作出某種決策，產(chǎn)生后一階段的狀態(tài)，這種關(guān)系描述了由k階段到k+1階段狀態(tài)的演變規(guī)律，稱為狀態(tài)轉(zhuǎn)移方程。動態(tài)規(guī)劃設(shè)計方法的一般模式動態(tài)規(guī)劃設(shè)計方法的一般模式 動態(tài)規(guī)劃所處理的問題是一個多階段決策問題，一般由初始狀態(tài)開始，通過對中間階段決策的選擇，達到結(jié)束狀態(tài)；或倒過來，從結(jié)束狀態(tài)開始，通過對中間階段決策的選擇，達到初始狀態(tài)。這些決策形成一個決策序列，同時確定了完成整個過程的一條活動路線，通常是求最優(yōu)活動路線。動態(tài)規(guī)劃的設(shè)計都有著一定的模式，一般要經(jīng)歷以下幾個步驟：w1、劃分階段 按照問題的時間或空間特征，把問題劃分為若干個

14、階段。在劃分階段時，注意劃分后的階段一定是有序的或者是可排序的，否則問題就無法求解。w2、確定狀態(tài)和狀態(tài)變量 將問題發(fā)展到各個階段時所處于的各種客觀情況用不同的狀態(tài)表示出來。當(dāng)然，狀態(tài)的選擇要滿足無后效性。w3、確定決策并寫出狀態(tài)轉(zhuǎn)移方程 因為決策和狀態(tài)轉(zhuǎn)移有著天然的聯(lián)系，狀態(tài)轉(zhuǎn)移就是根據(jù)上一階段的狀態(tài)和決策來導(dǎo)出本階段的狀態(tài)。所以如果確定了決策，狀態(tài)轉(zhuǎn)移方程也就可以寫出。但事實上常常是反過來做，根據(jù)相鄰兩段的各個狀態(tài)之間的關(guān)系來確定決策。w4、尋找邊界條件 給出的狀態(tài)轉(zhuǎn)移方程是一個遞推式，需要一個遞推的終止條件或邊界條件。動態(tài)規(guī)劃是最優(yōu)化算法動態(tài)規(guī)劃是最優(yōu)化算法 由于動態(tài)規(guī)劃的“名氣”如此之

15、大，以至于很多人甚至一些資料書上都往往把一種與動態(tài)規(guī)劃十分相似的算法，當(dāng)作是動態(tài)規(guī)劃。這種算法就是遞推。實際上，這兩種算法還是很容易區(qū)分的。 按解題的目標(biāo)來分，信息學(xué)試題主要分四類：判定性問題、構(gòu)造性問題、計數(shù)問題和最優(yōu)化問題。我們在競賽中碰到的大多是最優(yōu)化問題，而動態(tài)規(guī)劃正是解決最優(yōu)化問題的有力武器，因此動態(tài)規(guī)劃在競賽中的地位日益提高。而遞推法在處理判定性問題和計數(shù)問題方面也是一把利器。下面分別就兩個例子，談一下遞推法和動態(tài)規(guī)劃在這兩個方面的聯(lián)系?！纠纠?】數(shù)塔問題（數(shù)塔問題（IOI94）有形如圖所示的數(shù)塔，從頂部出發(fā)，在每一結(jié)點可以選擇向左走或是向右走，一起走到底層，要求找出一條路徑，使

16、路徑上的值最大。 這道題如果用枚舉法，在數(shù)塔層數(shù)稍大的情況下（如40），則需要列舉出的路徑條數(shù)將是一個非常龐大的數(shù)目。如果用貪心法又往往得不到最優(yōu)解。在用動態(tài)規(guī)劃考慮數(shù)塔問題時可以自頂向下的分析，自底向上的計算。從頂點出發(fā)時到底向左走還是向右走應(yīng)取決于是從左走能取到最大值還是從右走能取到最大值，只要左右兩道路徑上的最大值求出來了才能作出決策。同樣的道理下一層的走向又要取決于再下一層上的最大值是否已經(jīng)求出才能決策。這樣一層一層推下去，直到倒數(shù)第二層時就非常明了。所以實際求解時，可從底層開始，層層遞進，最后得到最大值。實際求解時應(yīng)掌握其編程的一般規(guī)律，通常需要哪幾個關(guān)鍵數(shù)組來存儲變化過程這一點非常

17、重要。 一般說來，很多最優(yōu)化問題都有著對應(yīng)的計數(shù)問題；反過來，很多計數(shù)問題也有著對應(yīng)的最優(yōu)化問題。因此，我們在遇到這兩類問題時，不妨多聯(lián)系、多發(fā)展，舉一反三，從比較中更深入地理解動態(tài)規(guī)劃的思想。 其實遞推和動態(tài)規(guī)劃這兩種方法的思想本來就很相似，也不必說是誰借用了誰的思想。關(guān)鍵在于我們要掌握這種思想，這樣我們無論在用動態(tài)規(guī)劃法解最優(yōu)化問題，或是在用遞推法解判定型、計數(shù)問題時，都能得心應(yīng)手、游刃有余了?！窘夥ㄒ弧浚嫱品ǎ窘夥ㄒ弧浚嫱品ǎ舅惴ǚ治觥俊舅惴ǚ治觥?貪心法往往得不到最優(yōu)解：本題若采用貪心法則：13-11-12-14-13，其和為63,但存在另一條路：13-8-26-15-24，其

18、和為86。 貪心法問題所在：眼光短淺。 動態(tài)規(guī)劃求解：動態(tài)規(guī)劃求解問題的過程歸納為：自頂向下的分析，自底向上計算。 其基本方法是： 劃分階段：按三角形的行，劃分階段，若有n行，則有n-1個階段。 A從根結(jié)點13出發(fā)，選取它的兩個方向中的一條支路，當(dāng)?shù)降箶?shù)第二層時，每個結(jié)點其后繼僅有兩個結(jié)點，可以直接比較，選擇最大值為前進方向，從而求得從根結(jié)點開始到底端的最大路徑。 B自底向上計算：（給出遞推式和終止條件） 從底層開始，本身數(shù)即為最大數(shù)； 倒數(shù)第二層的計算，取決于底層的數(shù)據(jù)：12+6=18，13+14=27，24+15=39，24+8=32； 倒數(shù)第三層的計算，取決于底二層計算的數(shù)據(jù)：27+12

19、=39，39+7=46，39+26=65 倒數(shù)第四層的計算，取決于底三層計算的數(shù)據(jù)：46+11=57，65+8=73 最后的路徑：138261524 C數(shù)據(jù)結(jié)構(gòu)及算法設(shè)計 圖形轉(zhuǎn)化：直角三角形，便于搜索：向下、向右 用三維數(shù)組表示數(shù)塔：ax,y,1表示行、列及結(jié)點本身數(shù)據(jù),ax,y,2能夠取得最大值,ax,y,3表示前進的方向0向下，1向右； 算法： 數(shù)組初始化，輸入每個結(jié)點值及初始的最大路徑、前進方向為0； 從倒數(shù)第二層開始向上一層求最大路徑，共循環(huán)N-1次； 從頂向下，輸出路徑：究竟向下還是向右取決于列的值，若列的值比原先多1則向右，否則向下?！緟⒖汲绦颉俊緟⒖汲绦颉縫rogram ex1

20、4_2_1;var a:array1.50,1.50,1.3 of longint; x,y,n:integer;begin write( please input the number of rows:); readln(n); for x:=1 to n do /輸入數(shù)塔的初始值 for y:=1 to x do begin read(ax,y,1); ax,y,2:=ax,y,1; ax,y,3:=0 /路徑走向，默認向下 end; for x:=n-1 downto 1 do for y:=1 to x do if ax+1,y,2ax+1,y+1,2 then /選擇路徑，保留最大路

21、徑值 begin ax,y,2:=ax,y,2+ax+1,y,2; ax,y,3:=0 end else begin ax,y,2:=ax,y,2+ax+1,y+1,2;ax,y,3:=1 end; writeln(max=,a1,1,2); /輸出數(shù)塔最大值 y:=1; for x:=1 to n-1 do /輸出數(shù)塔最大值的路徑 begin write(ax,y,1,- ); y:=y+ax,y,3 ; /下一行的列數(shù) end; writeln(an,y,1)end.輸入：5 /數(shù)塔層數(shù)1311 812 7 266 14 15 812 7 13 24 11輸出結(jié)果： max=86 13-8

22、-26-15-24【解法二】（順推法）【解法二】（順推法）【算法分析】【算法分析】 此題貪心法往往得不到最優(yōu)解，例如13-11-12-14-13其路徑的值為63，但這不是最優(yōu)解。 窮舉搜索往往是不可能的，當(dāng)層數(shù)N = 100時，路徑條數(shù)P = 299這是一個非常大的數(shù)，即使用世界上最快的電子計算機，也不能在規(guī)定時間內(nèi)計算出來。 對這道題唯一正確的方法是動態(tài)規(guī)劃。如果得到一條由頂?shù)降椎哪程幍囊粭l最佳路徑，那么對于該路徑上的每一個中間點來說，由頂點至該中間點的路徑所經(jīng)過的數(shù)字和也為最大。因此本題是一個典型的多階段決策最優(yōu)化問題。在本題中僅要求輸出最優(yōu)解，為此我們設(shè)置了數(shù)組Ai,j保存三角形數(shù)塔，B

23、i,j保存狀態(tài)值，按從上往下方式進行求解。 階段i：以層數(shù)來劃分階段，由從上往下方式計算層數(shù)1層數(shù)N（1in）；因此可通過第一重循環(huán) for i := 1 to n do begin 枚舉每一階段； 狀態(tài)Bi,j：由于每個階段中有多個狀態(tài)，因此可通過第二重循環(huán) for j := 1 to i do begin 求出每個階段的每個狀態(tài)的最優(yōu)解Bi,j； 決 策：每個狀態(tài)最多由上一層的兩個結(jié)點連接過來，因此不需要做循環(huán)?！緟⒖汲绦颉俊緟⒖汲绦颉縫rogram ex14_2_2;Var a,b : array1.100,0.100 of word; i,j,n : integer; max: wor

24、d;begin write(N = ); readln(n); fillchar(a,sizeof(a),0); for i := 1 to n do /輸入數(shù)塔的初始值 begin for j := 1 to i do read(ai,j); readln; end; b := a; b1,1 := a1,1; for i := 2 to n do /選擇路徑，保留最大路徑值 for j := 1 to i do if bi-1,j-1 bi-1,j then bi,j := bi-1,j-1+bi,j else bi,j := bi-1,j+bi,j; max := 0; for i :=

25、 1 to n do if bn,i max then max := bn,i; /在第n行中找出數(shù)塔最大值 writeln(Max = ,max); /輸出數(shù)塔最大值 readln;end.【例【例3】求最長不下降序列求最長不下降序列問題描述： 設(shè)有由n個不相同的整數(shù)組成的數(shù)列，記為:b(1)、b(2)、b(n)且b(i)b(j) (ij)，若存在i1i2i3 ie 且有b(i1)b(i2) b(ie)則稱為長度為e的不下降序列。程序要求，當(dāng)原數(shù)列出之后，求出最長的不下降序列。 例如13，7，9，16，38，24，37，18，44，19，21，22，63，15。例中13，16，18，19，2

26、1，22，63就是一個長度為7的不下降序列，同時也有7 ，9，16，18，19，21，22，63長度為8的不下降序列。算法分析： 根據(jù)動態(tài)規(guī)劃的原理，由后往前進行搜索(當(dāng)然從前往后也一樣)。 1對b(n)來說，由于它是最后一個數(shù)，所以當(dāng)從b(n)開始查找時，只存在長度為1的不下降序列； 2若從b(n-1)開始查找，則存在下面的兩種可能性： 若b(n-1)b(n)則存在長度為1的不下降序列b(n-1)或b(n)。 3一般若從b(i)開始，此時最長不下降序列應(yīng)該按下列方法求出:在b(i+1),b(i+2),b(n)中，找出一個比b(i)大的且最長的不下降序列，作為它的后繼。數(shù)據(jù)結(jié)構(gòu)： 為算法上的需

27、要，定義一個整數(shù)類型二維數(shù)組b(N,3) 1b(I,1)表示第I個數(shù)的數(shù)值本身； 2b(I,2)表示從I位置到達N的最長不下降序列長度 3b(I,3)表示從I位置開始最長不下降序列的下一個位置，若bI,3=0則表示后面沒有連接項。 求解過程： 從倒數(shù)第二項開始計算，后面僅有1項，比較一次，因6315，不符合要求，長度仍為1。 從倒數(shù)第三項開始其后有2項，需做兩次比較，得到目前最長的不下降序列為2，如下表：11121314111213142263152122631521132111300121300 一般處理過程是： 在i+1,i+2,n項中，找出比bI,1大的最長長度L以及位置K; 若L0，則

28、bI,2:=L+1;bI,3:=k; 最后本題經(jīng)過計算，其數(shù)據(jù)存儲表如下：1234567891011121314137916382437184419212263157876343524321434897910131112130初始化: for i:=1 to n do begin read(bi,1); bi,2:=1;bi,3:=0; end;下面給出求最長不下降序列的算法: for i:=n-1 downto 1 do begin L:=0;k:=0; for j:=i+1 to n do if(bj,1bi,1)and(bj,2L) then begin L:=bj,2; k:=j; e

29、nd; if L0 then begin bi,2:=L+1; bi,3:=k; end; end;下面找出最長不下降序列： k:=1; for j:=1 to n do if bj,2bk,2 then k:=j; 最長不下降序列長度為B(k, 2)序列 while k0 do begin write(bk,1:4); k:=bk,3; end;【參考程序】program ex14_3;var n,i,L,k,j:integer; b:array1.100,1.3of integer;begin writeln(input n:); readln(n); for i:=1 to n do /

30、輸入序列的初始值 begin read(bi,1); bi,2:=1;bi,3:=0; end; for i:=n-1 downto 1 do /求最長不下降序列求最長不下降序列 begin L:=0;k:=0; for j:=i+1 to n do if(bj,1bi,1)and(bj,2L) then begin L:=bj,2; k:=j; end; if L0 then begin bi,2:=L+1;bi,3:=k; end; end; k:=1; for j:=1 to n do /求最長不下降序列的起始位置求最長不下降序列的起始位置 if bj,2bk,2 then k:=j;

31、writeln(max=,bk,2); /輸出結(jié)果輸出結(jié)果 while k0 do /輸出最長不下降序列輸出最長不下降序列 begin write(bk,1:4); k:=bk,3; end; writeln; readln;end.程序運行結(jié)果：輸入：1413 7 9 16 38 24 37 18 44 19 21 22 63 15輸出：max=87 9 16 18 19 21 22 63【例【例4】攔截導(dǎo)彈攔截導(dǎo)彈1(Noip1999) 某國為了防御敵國的導(dǎo)彈襲擊，發(fā)展出一種導(dǎo)彈攔截系統(tǒng)。但是這種攔截系統(tǒng)有一個缺陷：雖然它的第一發(fā)炮彈能夠到達任意的高度，但是以后每一發(fā)炮彈都不能高于前一發(fā)的

32、高度。某天，雷達捕捉到敵國的導(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è)置了一張記憶表Ci，在按從后往前方式求解的過程中，將每一個子問題的最佳決策保存起來，避免在輸出方案時重復(fù)計算。階段i：由右而左計算導(dǎo)彈n導(dǎo)彈1中可攔截的最多導(dǎo)彈數(shù)（1in）； 狀態(tài)Bi：由于每個

33、階段中僅一個狀態(tài)，因此可通過一重循環(huán) for i := n-1 downto 1 do 枚舉每個階段的狀態(tài)Bi； 決策k：在攔截導(dǎo)彈i之后應(yīng)攔截哪一枚導(dǎo)彈可使得Bi最大（i+1kn）， 1 2 3 4 5 6 7 8 9 10 11 12 13 14 I13 7 9 16 38 24 37 18 44 19 21 22 63 15 AI /高度2 1 1 2 4 3 3 2 3 2 2 2 2 1 BI /可攔截數(shù)2 0 0 14 6 8 8 14 10 14 14 14 14 0 CI /再攔截 【參考程序】（逆推法）【參考程序】（逆推法）program ex14_4_1;Var a,b,c

34、: array1.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(an); bn := 1; cn := 0; end; readln; for i := n-1 downto 1 do begin /枚舉每一個階段的狀態(tài)，設(shè)導(dǎo)彈i被攔截 max := 0; k := 0; for j := i+1 to n do /枚舉決策，計算最佳方案中攔截的下一枚導(dǎo)彈 if (aj max) then begin max := bj

35、; k := j; end; bi := max+1; ci := k; /若導(dǎo)彈i之后攔截導(dǎo)彈k為最佳方案，則記下 end; max := 0; for i := 1 to n do /枚舉求出一套系統(tǒng)能攔截的最多導(dǎo)數(shù) if bi max then begin max := bi; k := i; end; writeln(Max = ,bk); /打印輸出結(jié)果 while k 0 do begin write(ak:5); k := ck; end; readln;end.【例【例5】攔截導(dǎo)彈攔截導(dǎo)彈2(Noip1999) 某國為了防御敵國的導(dǎo)彈襲擊，發(fā)展出一種導(dǎo)彈攔截系統(tǒng)。但是這種導(dǎo)彈攔

36、截系統(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 OUTPUT389 207 155 300 299 170 158 65 6（最多能攔截的導(dǎo)彈數(shù)） 2（要攔截所有導(dǎo)彈最少要配備的系統(tǒng)數(shù)）【算法分析】【算法分析】 第一問即經(jīng)典的最長不下降子序列問題，可以用一般的DP算法，也可以用高效算法，但這個題的數(shù)據(jù)規(guī)模好像不需要。高效算法是這樣的：用ax表示原序列中第x個元素，bx表示長度為x的不下降子序列的最后一個元素的最小值，b數(shù)組初值為無窮大。容易看出，這個數(shù)組是遞減的（當(dāng)然可能有相鄰兩個元素相等）。當(dāng)處理第ax時，用二分法查找它可以連接到長度