noip動態(tài)規(guī)劃教學(xué)PPT

1、動態(tài)程序設(shè)計 動態(tài)規(guī)劃動態(tài)規(guī)劃 與遞歸程序相類，將對問題求解分解為對子問與遞歸程序相類，將對問題求解分解為對子問 題求解；不同之處在于把子問題的解存起來，題求解；不同之處在于把子問題的解存起來， 用空間換時間。用空間換時間。 例：例：fibonacci數(shù)數(shù) uf(0)=0; f(1)=1; f(n)=f(n-1)+f(n-2); u遞歸遞歸: f(n-1)和和f(n-2)分別求到底一次分別求到底一次 u動態(tài)規(guī)劃：用數(shù)組將前動態(tài)規(guī)劃：用數(shù)組將前n-1個數(shù)存起來，每次只用個數(shù)存起來，每次只用 一個加法一個加法 fn = fn-1+fn-2 即可。即可。 例最短路徑問題。下圖中給出一個地圖，地圖中每

2、個頂點(diǎn)代表例最短路徑問題。下圖中給出一個地圖，地圖中每個頂點(diǎn)代表 一個城市，兩個城市之間的連線表示道路，連線上的數(shù)值代表道路一個城市，兩個城市之間的連線表示道路，連線上的數(shù)值代表道路 的長度?，F(xiàn)在，想從城市的長度。現(xiàn)在，想從城市a到城市到城市e，怎樣走路程最短，最短路程，怎樣走路程最短，最短路程 的長度是多少？的長度是多少？ 現(xiàn)在，我們想從城市現(xiàn)在，我們想從城市a到達(dá)城市到達(dá)城市e。怎樣走才能使得路徑最短，最。怎樣走才能使得路徑最短，最 短路徑的長度是多少？短路徑的長度是多少？ 設(shè)：設(shè)：disx為城市為城市x到城市到城市e的最短路徑長度（的最短路徑長度（x表示任意一個城市）表示任意一個城市）;

3、mapi,j表示表示i，j 兩個城市間的距離，若兩個城市間的距離，若mapi,j=0，則兩個城市不通。，則兩個城市不通。 我們可以使用回溯來計算我們可以使用回溯來計算disx: var s:未訪問的城市聚合；未訪問的城市聚合； function search(who):integer; 求城市求城市who與城市與城市e的最短距離的最短距離 var i,j,min:integer; begin if who=e then search:=0 else begin min:=maxint; for i取遍所有城市取遍所有城市 do if (mapwho,i0) and (i in s) then

4、begin s:=s-i; 城市城市i已訪問已訪問 j:=mapwho,i+search(i); 計算城市計算城市e至城市至城市who的路徑長度的路徑長度 s:=s+i; 恢復(fù)城市恢復(fù)城市i未訪問狀態(tài)未訪問狀態(tài) if jmin then min:=j; 若城市若城市e至城市至城市who的路徑長度為目前最短，則記下的路徑長度為目前最短，則記下 end; search:=min; 返回城市返回城市e至城市的最短路徑長度至城市的最短路徑長度 end; begin s:=所有城市；所有城市； disa:=search(a); 計算城市計算城市a城市城市e的最短路徑長度的最短路徑長度 writeln(d

5、ista); end. 這個程序的效率如何呢？我們可以看到，每次除了已經(jīng)訪問過的城市外，這個程序的效率如何呢？我們可以看到，每次除了已經(jīng)訪問過的城市外， 其他城市都要，所以時間復(fù)雜度為其他城市都要，所以時間復(fù)雜度為w(n!)，這是一個，這是一個“指數(shù)級指數(shù)級”的算法。的算法。 那么還有沒有效率更高的解題方法呢？那么還有沒有效率更高的解題方法呢？ 首先，我們來觀察上述算法。在求首先，我們來觀察上述算法。在求b1到到e的最短路徑的時候，先求出從的最短路徑的時候，先求出從c2 到到e的最短路徑；而在求的最短路徑；而在求b2到到e的最短路徑的時候，又求了一遍從的最短路徑的時候，又求了一遍從c2到到e

6、的最短路徑。也就是說，從的最短路徑。也就是說，從c2到到e的最短路徑求了兩遍。兩樣可以發(fā)現(xiàn)，的最短路徑求了兩遍。兩樣可以發(fā)現(xiàn)， 在求從在求從c1、c2到到e的最短路徑的過程中，從的最短路徑的過程中，從d1到到e的最短路徑也被求了兩的最短路徑也被求了兩 遍。而在整個過程中，從遍。而在整個過程中，從d1到到e的最短路徑被求了四遍，這是多么大的一的最短路徑被求了四遍，這是多么大的一 個浪費(fèi)??！如果在求解的過程中，同時將求得的最短路徑的距離個浪費(fèi)??！如果在求解的過程中，同時將求得的最短路徑的距離“記錄在記錄在 案案”，以便將來隨時調(diào)用，則可以避免這種重復(fù)計算。至此，一個新的思，以便將來隨時調(diào)用，則可以

7、避免這種重復(fù)計算。至此，一個新的思 路產(chǎn)生了，即由后往前依次推出每個路產(chǎn)生了，即由后往前依次推出每個dis值，直到推出值，直到推出disa為止為止。 階段的劃分具有如下性質(zhì)：階段的劃分具有如下性質(zhì)： 階段階段i的取值只與階段的取值只與階段i+1有關(guān)，階段有關(guān)，階段i+1的取值只對階段的取值只對階段i的取值的取值 產(chǎn)生影響；產(chǎn)生影響； 每個階段的順序是確定的，不可以調(diào)換任兩個階段的順序。每個階段的順序是確定的，不可以調(diào)換任兩個階段的順序。 abcde 階段階段1階段階段2階段階段3階段階段4階段階段0 我們從階段我們從階段4的城市的城市e出發(fā)，按照階段的順序倒推至階段出發(fā)，按照階段的順序倒推至階

8、段0的城市的城市a。 在求解的各個階段，利用了在求解的各個階段，利用了k階段與階段與k+1階段之間的如下關(guān)系階段之間的如下關(guān)系 diskx= dis4e=0 k=4k=4，3 3，0 0，其中，其中disdisk kx x指指k k階段的城市階段的城市x x。 ),( ,min 1 gyxyxmapydis ky 階段的城市集 e d3 d1 d2 c1 c3 c2a b3 b2 b1 5 4 2 6 3 4 6 5 6 12 2 2 3 3 2 3 4 0 abcde 階段階段1 階段階段2 階段階段3階段階段4階段階段0 我們從階段我們從階段4的城市的城市e出發(fā)，按照階段的順序倒推至階段出

9、發(fā)，按照階段的順序倒推至階段0的城市的城市a。 在求解的各個階段，利用了在求解的各個階段，利用了k階段與階段與k+1階段之間的如下關(guān)系階段之間的如下關(guān)系 diskx= dis4e=0 k=4k=4，3 3，0 0，其中，其中disdisk kx x指指k k階段的城市階段的城市x x。 ),( ,min 1 gyxyxmapydis ky 階段的城市集 e d3 d1 d2 c1 c3 c2a b3 b2 b1 5 4 2 6 3 4 6 5 6 12 2 2 3 3 2 3 4 0 2 3 4 abcde 階段階段1 階段階段2 階段階段3階段階段4階段階段0 我們從階段我們從階段4的城市的

10、城市e出發(fā)，按照階段的順序倒推至階段出發(fā)，按照階段的順序倒推至階段0的城市的城市a。 在求解的各個階段，利用了在求解的各個階段，利用了k階段與階段與k+1階段之間的如下關(guān)系階段之間的如下關(guān)系 diskx= dis4e=0 k=4k=4，3 3，0 0，其中，其中disdisk kx x指指k k階段的城市階段的城市x x。 ),( ,min 1 gyxyxmapydis ky 階段的城市集 23 e d3 d1 d2 c1 c3 c2a b3 b2 b1 5 4 2 6 3 4 6 5 6 12 2 2 3 3 2 3 4 0 3 4 4 6 abcde 階段階段1 階段階段2 階段階段3階段

11、階段4階段階段0 我們從階段我們從階段4的城市的城市e出發(fā)，按照階段的順序倒推至階段出發(fā)，按照階段的順序倒推至階段0的城市的城市a。 在求解的各個階段，利用了在求解的各個階段，利用了k階段與階段與k+1階段之間的如下關(guān)系階段之間的如下關(guān)系 diskx= dis4e=0 k=4k=4，3 3，0 0，其中，其中disdisk kx x指指k k階段的城市階段的城市x x。 ),( ,min 1 gyxyxmapydis ky 階段的城市集 e d3 d1 d2 c1 c3 c2a b3 b2 b1 5 4 2 6 3 4 6 5 6 12 2 2 3 3 2 3 4 0 2 3 4 3 4 6

12、7 7 8 abcde 階段階段1 階段階段2 階段階段3階段階段4階段階段0 我們從階段我們從階段4的城市的城市e出發(fā)，按照階段的順序倒推至階段出發(fā)，按照階段的順序倒推至階段0的城市的城市a。 在求解的各個階段，利用了在求解的各個階段，利用了k階段與階段與k+1階段之間的如下關(guān)系階段之間的如下關(guān)系 diskx= dis4e=0 k=4k=4，3 3，0 0，其中，其中disdisk kx x指指k k階段的城市階段的城市x x。 ),( ,min 1 gyxyxmapydis ky 階段的城市集 e d3 d1 d2 c1 c3 c2a b3 b2 b1 5 4 2 6 3 4 6 5 6

13、12 2 2 3 3 2 3 4 0 2 3 4 3 4 6 7 7 8 10 abcde 階段階段1 階段階段2 階段階段3階段階段4階段階段0 由此得出程序由此得出程序 : dise0； for k3 downto 0 do3 downto 0 do for x for x取遍取遍k階段的所有城市階段的所有城市do begin disx； for y取遍取遍k+1階段的所有城市階段的所有城市do if disy+mapx,yfi+1,j+1 then fi,j:=fi+1,j+ai,j else fi,j:=fi+1,j+1+ai,j; 狀態(tài)轉(zhuǎn)移方程：狀態(tài)轉(zhuǎn)移方程：fi,j:=max(fi

14、+1,j+1, fi+1,j)+ai,j; program triple; const fin=d:input.txt; fon=d:output.txt; maxn=100; var f,a:array1.maxn,1.maxn of integer; n:integer; procedure init; procedure main; procedure print; begin init; main; print; end. procedure init; var i,j:integer; begin assign(input,fin);reset(input); readln(n);

15、for i:=1 to n do begin for j:=1 to i do read(ai,j); readln; end; close(input); end; procedure print; var i,ans:integer; begin assign(output,fon); rewrite(output); writeln(f1,1); close(output); end; procedure main; var i,j:integer; begin for i:=1 to n do fn,i:=an,i; for i:=n-1 downto 1 do for j:=1 to

16、 i do if fi+1,jfi+1,j+1 then fi,j:=fi+1,j+ai,j else fi,j:=fi+1,j+1+ai,j; end; program triple; const fin=d:input.txt; fon=d:output.txt; maxn=100; var f,a:array1.maxn,1.maxn of integer; n:integer; procedure init; var i,j:integer; begin assign(input,fin);reset(input); readln(n); for i:=1 to n do begin

17、for j:=1 to i do read(ai,j); readln; end; close(input); end; procedure main; var i,j:integer; begin for i:=1 to n do fn,i:=an,i; for i:=n-1 downto 1 do for j:=1 to i do if fi+1,jfi+1,j+1 then fi,j:=fi+1,j+ai,j else fi,j:=fi+1,j+1+ai,j; end; procedure print; var i,ans:integer; begin assign(output,fon

18、); rewrite(output); writeln(f1,1); close(output); end; begin init; main; print; end. 例例2 給定數(shù)列給定數(shù)列a1,a2,an，求最長遞減子序列。，求最長遞減子序列。 輸入數(shù)據(jù)輸入數(shù)據(jù) n和和n個整數(shù)（個整數(shù)（n=1000）。）。 輸出數(shù)據(jù)輸出數(shù)據(jù) 最長遞減子序列。最長遞減子序列。 算法分析算法分析 ai=數(shù)列的第數(shù)列的第i個數(shù)；個數(shù)； si=以以ai結(jié)尾的最長遞減子序列長度；結(jié)尾的最長遞減子序列長度； si=maxsk+1 0=kai； 邊界條件：邊界條件：s0=0； answer=maxsi, 1=i=n。

19、 a: 76 8 9 6 20 19 18 69 3 s: 1 2 2 3 2 3 4 2 5 算法分析算法分析 ai=數(shù)列的第數(shù)列的第i個數(shù)；個數(shù)； si=以以ai結(jié)尾的最長遞減子序列長度；結(jié)尾的最長遞減子序列長度； a: 76 8 9 6 20 19 18 69 3 s: 1 2 2 3 2 3 4 2 5 狀態(tài)轉(zhuǎn)移方程：狀態(tài)轉(zhuǎn)移方程：si=maxsk+1 0=kai； 邊界條件：邊界條件：s0=0； answer=maxsi, 1=iai) and (sk+1si) then si:=sk+1; if (sianswer) then answer:=si; end; writeln(an

20、swer); si=maxsk+1 0=kai； 邊界條件：邊界條件：s0=0； answer=maxsi, 1=iai) and (sk+1si) then si:=sk+1; if (sianswer) then answer:=si; end; writeln(answer); end. program ex6_2_2; var n,i,k,answer:integer; a:array1.1000 of integer; s,last:array0.1000 of integer; size:integer; q:array1.1000 of integer; begin read(n

21、); for i:=1 to n do read(ai); s0:=0; answer:=0; for i:=1 to n do begin si:=0; for k:=0 to i-1 do if (k=0) or (akai) and (sk+1si) then begin si:=sk+1; lasti:=k; end; end; for i:=1 to n do if (sianswer) then begin answer:=si; k:=i; end; size:=0; repeat inc(size); qsize:=k; k:=lastk; until k=0; writeln

22、(answer); for i:=size downto 1 do write(qi, ); writeln; end. 轉(zhuǎn)移方程轉(zhuǎn)移方程 數(shù)的計算數(shù)的計算(02)：fi:=1+f1+f2+fi div 2 過河卒過河卒(02)：fi,j = fi-1,j + fi,j-1 棧棧(noip2003)：fi,j=fi-1,j+1+fi-1,j; 傳球游戲傳球游戲(08)：fi,k:=fi-1,k-1+fi+1,k-1; 裝箱問題裝箱問題(01) ：f(x)=maxf(x-wi)+ui 當(dāng)當(dāng)x=wi,1=i=n 采藥采藥(05)： f(i,x)=max(f(i,x-wi)+ui,f(i-1,x);f(n,m) 開心的金明開心的金明(06) 擺花擺花(12)：fi,j:=(fi,j+fi-1,j-k)mod 1000007 數(shù)字游戲數(shù)字游戲(03 )：fmin1p,i,j=minfmin1p-1,i,k*gk+1,j (i=k=j-1)