動態(tài)規(guī)劃基礎講解及經典案例分析解答PPT演示課件

1、1第九課動態(tài)規(guī)劃動態(tài)規(guī)劃( (i) )綜合實踐考核2數字三角形 1、問題描述、問題描述 上圖給出了一個數字三角形。從三角形的頂部到底部有很多條上圖給出了一個數字三角形。從三角形的頂部到底部有很多條不同的路徑。對于每條路徑，把路徑上面的數加起來可以得到不同的路徑。對于每條路徑，把路徑上面的數加起來可以得到一個和，和最大的路徑稱為最佳路徑。你的任務就是求出最佳一個和，和最大的路徑稱為最佳路徑。你的任務就是求出最佳路徑上的數字之和。路徑上的數字之和。注意：路徑上的每一步只能從一個數走到下一層上和它最近的注意：路徑上的每一步只能從一個數走到下一層上和它最近的左邊的數或者右邊的數。左邊的數或者右邊的數。

2、3問題描述輸入數據輸入數據輸入的第一行是一個整數輸入的第一行是一個整數n (1 n = 100)，給出，給出三角形的行數。下面的三角形的行數。下面的n 行給出數字三角形。數字三行給出數字三角形。數字三角形上的數的范圍都在角形上的數的范圍都在0 和和100 之間。之間。輸出要求輸出要求輸出最大的和。輸出最大的和。4問題描述輸入樣例輸入樣例573 88 1 02 7 4 44 5 2 6 5輸出樣例輸出樣例3052、解題思路 這道題目可以用遞歸的方法解決。基本思路是：這道題目可以用遞歸的方法解決。基本思路是：以以d( r, j)表示第表示第r 行第行第 j 個數字個數字(r，j 都從都從1 開始算

3、開始算)，以，以maxsum(r, j) 代表從第代表從第 r 行的第行的第 j 個數字到底邊的最佳路徑個數字到底邊的最佳路徑的數字之和，則本題是要求的數字之和，則本題是要求 maxsum(1, 1) 。從某個從某個d(r, j)出發(fā)，顯然下一步只能走出發(fā)，顯然下一步只能走d(r+1, j)或者或者d(r+1, j+1)。如果走。如果走d(r+1, j)，那么得到的，那么得到的maxsum(r, j)就是就是maxsum(r+1, j) + d(r, j)；如果走；如果走d(r+1, j+1)，那么得，那么得到的到的maxsum(r, j)就是就是maxsum(r+1, j+1) + d(r,

4、 j)。所。所以，選擇往哪里走，就看以，選擇往哪里走，就看maxsum(r+1, j)和和maxsum(r+1, j+1)哪個更大了。哪個更大了。63、參考程序 i#include #define max_num 100int dmax_num + 10max_num + 10;int n;int maxsum( int r, int j)if( r = n )return drj;int nsum1 = maxsum(r+1, j);int nsum2 = maxsum(r+1, j+1);if( nsum1 nsum2 )return nsum1+drj;return nsum2+drj;

5、 73、參考程序 iint main(void)int m;scanf(%d, &n);for( int i = 1; i = n; i + )for( int j = 1; j = i; j + )scanf(%d, &dij);printf(%d, maxsum(1, 1);return 0;提交結果：提交結果：time limit exceed8程序i分析 上面的程序，效率非常低，在上面的程序，效率非常低，在n 值并不大，值并不大，比如比如n=100 的時候，就慢得幾乎永遠算不出的時候，就慢得幾乎永遠算不出結果了。結果了。為什么會這樣呢？是因為過多的重復計算。為什么會這樣

6、呢？是因為過多的重復計算。我們不妨將對我們不妨將對maxsum 函數的一次調用稱為函數的一次調用稱為一次計算。那么，每次計算一次計算。那么，每次計算maxsum(r, j)的的時候，都要計算一次時候，都要計算一次maxsum(r+1, j+1)，而每次計算而每次計算maxsum(r, j+1)的時候，也要的時候，也要計算一次計算一次maxsum(r+1, j+1)。重復計算因。重復計算因此產生。此產生。在 題 目 中 給 出 的 例 子 里 ， 如 果 我 們 將在 題 目 中 給 出 的 例 子 里 ， 如 果 我 們 將maxsum(r, j)被計算的次數都寫在位置（被計算的次數都寫在位置

7、（r, j），那么就能得到右面的三角形：），那么就能得到右面的三角形：11 11 2 11 3 3 11 4 6 4 173 88 1 02 7 4 44 5 2 6 59程序分析 n 從上圖可以看出，最后一行的計算次數總和是從上圖可以看出，最后一行的計算次數總和是16，倒數第二行，倒數第二行的計算次數總和是的計算次數總和是8。不難總結出規(guī)律，對于。不難總結出規(guī)律，對于n 行的三角形，總行的三角形，總的計算次數是的計算次數是20 +21+22+2(n-1)=2n-1。當。當n= 100 時，總的計算次數是一個讓人無法接受的大數字。時，總的計算次數是一個讓人無法接受的大數字。n 既然問題出在重復

8、計算，那么解決的辦法，當然就是，一個值既然問題出在重復計算，那么解決的辦法，當然就是，一個值一旦算出來，就要記住，以后不必重新計算。即第一次算出一旦算出來，就要記住，以后不必重新計算。即第一次算出maxsum(r, j)的值時，就將該值存放起來，下次再需要計算的值時，就將該值存放起來，下次再需要計算maxsum(r, j)時，直接取用存好的值即可，不必再次調用時，直接取用存好的值即可，不必再次調用maxsum 進行函數遞歸計算了。這樣，每個進行函數遞歸計算了。這樣，每個maxsum(r, j)都只都只需要計算需要計算1 次即可，那么總的計算次數（即調用次即可，那么總的計算次數（即調用maxsu

9、m 函數的函數的次數）就是三角形中的數字總數，即次數）就是三角形中的數字總數，即1+2+3+n = n(n+1)/2。n 如何存放計算出來的如何存放計算出來的maxsum（r, j）值呢？顯然，用一個二維）值呢？顯然，用一個二維數組數組amaxsumnn就能解決。就能解決。amaxsumrj就存放就存放maxsum(r, j)的計算結果。下次再需要的計算結果。下次再需要maxsum(r, j)的值時，的值時，不必再調用不必再調用maxsum 函數，只需直接取函數，只需直接取amaxsumrj的值即的值即可?？伞?04、參考程序 ii#include #include #define max_n

10、um 100int dmax_num + 10max_num + 10;int n;int amaxsummax_num + 10max_num + 10;int maxsum( int r, int j) if( r = n ) return drj; if( amaxsumr+1j = -1 ) /如果如果maxsum(r+1, j)沒有計算過沒有計算過 amaxsumr+1j = maxsum(r+1, j); if( amaxsumr+1j+1 = -1) amaxsumr+1j+1 = maxsum(r+1, j+1); if( amaxsumr+1j amaxsumr+1j+1 )

11、 return amaxsumr+1j +drj; return amaxsumr+1j+1 + drj;114、參考程序 iiint main(void) int m; scanf(%d, & n); /將將 amaxsum 全部置成全部置成-1, 開始時所有的開始時所有的 maxsum(r, j)都沒有算過都沒有算過 memset(amaxsum, -1, sizeof(amaxsum); for( int i = 1; i = n; i + ) for( int j = 1; j = i; j + ) scanf(%d, & dij); printf(%d, maxsum

12、(1, 1); return 0;12程序ii分析 這種將一個問題分解為子問題遞歸求解，并且將中間結果這種將一個問題分解為子問題遞歸求解，并且將中間結果保存以避免重復計算的辦法，就叫做保存以避免重復計算的辦法，就叫做“動態(tài)規(guī)劃動態(tài)規(guī)劃”。動態(tài)規(guī)動態(tài)規(guī)劃通常用來求最優(yōu)解，能用動態(tài)規(guī)劃解決的求最優(yōu)解問題，劃通常用來求最優(yōu)解，能用動態(tài)規(guī)劃解決的求最優(yōu)解問題，必須滿足，最優(yōu)解的每個局部解也都是最優(yōu)的。必須滿足，最優(yōu)解的每個局部解也都是最優(yōu)的。以上題為例，以上題為例，最佳路徑上面的每個數字到底部的那一段路徑，都是從該數最佳路徑上面的每個數字到底部的那一段路徑，都是從該數字出發(fā)到達到底部的最佳路徑。字出發(fā)

13、到達到底部的最佳路徑。實際上，遞歸的思想在編程時未必要實現為遞歸函數。在上實際上，遞歸的思想在編程時未必要實現為遞歸函數。在上面的例子里，有遞推公式：面的例子里，有遞推公式： drj rnamaxsumrjmax(amaxsumr1j, amaxsumr1j1)drj 其其他他因此，不需要寫遞歸函數，從因此，不需要寫遞歸函數，從amaxsumn-1這一行元素這一行元素開始向上逐行遞推，就能求得開始向上逐行遞推，就能求得amaxsum11的值了。的值了。135、參考程序 iiiint dmax_num + 10max_num + 10;int n;int amaxsummax_num + 10m

14、ax_num + 10;int main(void) int i, j; scanf(%d, & n); for( i = 1; i = n; i + ) for( j = 1; j = i; j + ) scanf(%d, &dij); for( j = 1; j 1 ; i - ) for( j = 1; j amaxsumij+1 ) amaxsumi-1j = amaxsumij + di-1j; else amaxsumi-1j = amaxsumij+1 + di-1j; printf(%d, amaxsum11); return 0;思考題思考題：上面的幾個程序：

15、上面的幾個程序只算出了最佳路徑的數字只算出了最佳路徑的數字之和。如果要求輸出最佳之和。如果要求輸出最佳路徑上的每個數字，該怎路徑上的每個數字，該怎么辦？么辦？14動態(tài)規(guī)劃解題的一般思路 n 許多求最優(yōu)解的問題可以用動態(tài)規(guī)劃來解決。許多求最優(yōu)解的問題可以用動態(tài)規(guī)劃來解決。n 首先要把原問題分解為若干個子問題。注意單純的遞歸往往會導首先要把原問題分解為若干個子問題。注意單純的遞歸往往會導致子問題被重復計算，用動態(tài)規(guī)劃的方法，子問題的解一旦求出就致子問題被重復計算，用動態(tài)規(guī)劃的方法，子問題的解一旦求出就要被保存，所以每個子問題只需求解一次。要被保存，所以每個子問題只需求解一次。 n 子問題經常和原問

16、題形式相似，有時甚至完全一樣，只不過規(guī)模子問題經常和原問題形式相似，有時甚至完全一樣，只不過規(guī)模從原來的從原來的n 變成了變成了n-1，或從原來的，或從原來的nm 變成了變成了n(m-1) 等等等。等。n 找到子問題，就意味著找到了將整個問題逐漸分解的辦法。找到子問題，就意味著找到了將整個問題逐漸分解的辦法。n 分解下去，直到最底層規(guī)模最小的的子問題可以一目了然地看出分解下去，直到最底層規(guī)模最小的的子問題可以一目了然地看出解。解。n 每一層子問題的解決，會導致上一層子問題的解決，逐層向上，每一層子問題的解決，會導致上一層子問題的解決，逐層向上，就會導致最終整個問題的解決。就會導致最終整個問題的

17、解決。n 如果從最底層的子問題開始，自底向上地推導出一個個子問題的如果從最底層的子問題開始，自底向上地推導出一個個子問題的解，那么編程的時候就不需要寫遞歸函數。解，那么編程的時候就不需要寫遞歸函數。15動態(tài)規(guī)劃解題的一般思路 n 用動態(tài)規(guī)劃解題時，將和子問題相關的各個變量的一組取值，用動態(tài)規(guī)劃解題時，將和子問題相關的各個變量的一組取值，稱之為一個稱之為一個“狀態(tài)狀態(tài)”。一個。一個“狀態(tài)狀態(tài)”對應于一個或多個子問題，對應于一個或多個子問題，所謂某個所謂某個“狀態(tài)狀態(tài)”下的下的“值值”，就是這個，就是這個“狀態(tài)狀態(tài)”所對應的子所對應的子問題的解。問題的解。n 比如數字三角形，子問題就是比如數字三角

18、形，子問題就是“從位于從位于(r，j)數字開始，到數字開始，到底邊路徑的最大和底邊路徑的最大和”。這個子問題和兩個變量。這個子問題和兩個變量r 和和j 相關，那相關，那么一個么一個“狀態(tài)狀態(tài)”，就是，就是r, j 的一組取值，即每個數字的位置就的一組取值，即每個數字的位置就是一個是一個“狀態(tài)狀態(tài)”。該。該“狀態(tài)狀態(tài)”所對應的所對應的“值值”，就是從該位置，就是從該位置的數字開始，到底邊的最佳路徑上的數字之和。的數字開始，到底邊的最佳路徑上的數字之和。n 定義出什么是定義出什么是“狀態(tài)狀態(tài)”，以及在該，以及在該 “狀態(tài)狀態(tài)”下的下的“值值”后，后，就要找出不同的狀態(tài)之間如何遷移就要找出不同的狀態(tài)

19、之間如何遷移即如何從一個或多個即如何從一個或多個“值值”已知的已知的 “狀態(tài)狀態(tài)”，求出另一個，求出另一個“狀態(tài)狀態(tài)”的的“值值”。狀。狀態(tài)的遷移可以用遞推公式表示，此遞推公式也可被稱作態(tài)的遷移可以用遞推公式表示，此遞推公式也可被稱作“狀態(tài)狀態(tài)轉移方程轉移方程”。16動態(tài)規(guī)劃解題的一般思路 n用動態(tài)規(guī)劃解題，如何尋找用動態(tài)規(guī)劃解題，如何尋找“子問題子問題”，定義，定義“狀態(tài)狀態(tài)”，“狀態(tài)轉移方程狀態(tài)轉移方程”是什么樣的，并沒有一定之規(guī)，需要具體問是什么樣的，并沒有一定之規(guī)，需要具體問題具體分析，題目做多了就會有感覺。題具體分析，題目做多了就會有感覺。n甚至，對于同一個問題，分解成子問題的辦法可

20、能不止一種，甚至，對于同一個問題，分解成子問題的辦法可能不止一種，因而因而“狀態(tài)狀態(tài)”也可以有不同的定義方法。不同的也可以有不同的定義方法。不同的“狀態(tài)狀態(tài)”定義定義方法可能會導致時間、空間效率上的區(qū)別。方法可能會導致時間、空間效率上的區(qū)別。 drj rnamaxsumrjmax(amaxsumr1j, amaxsumr1j1)drj 其其他他17最長上升子序列 1、問題描述、問題描述 一個數的序列一個數的序列bi，當，當b1 b2 . bs 的時候，的時候，我們稱這個序列是上升的。對于給定的一個序列我們稱這個序列是上升的。對于給定的一個序列(a1, a2, ., an)，我們可以得到一些上升

21、的子序列，我們可以得到一些上升的子序列(ai1, ai2, ., aik)，這里，這里1 = i1 i2 . ik = n。比如，對于序列比如，對于序列(1, 7, 3, 5, 9, 4, 8)，有它的一些上，有它的一些上升子序列，如升子序列，如(1, 7), (3, 4, 8)等等。這些子序列中等等。這些子序列中最長的長度是最長的長度是4，比如子序列，比如子序列(1, 3, 5, 8).你的任務，就是對于給定的序列，求出最長上升子序你的任務，就是對于給定的序列，求出最長上升子序列的長度。列的長度。18問題描述輸入數據輸入數據輸入的第一行是序列的長度輸入的第一行是序列的長度n (1 = n =

22、 1000)。第二行。第二行給出序列中的給出序列中的n 個整數，這些整數的取值范圍都在個整數，這些整數的取值范圍都在0 到到10000。輸出要求輸出要求最長上升子序列的長度。最長上升子序列的長度。輸入樣例輸入樣例71 7 3 5 9 4 8輸出樣例輸出樣例4192、解題思路 n 如何把這個問題分解成子問題呢？經過分析，發(fā)現如何把這個問題分解成子問題呢？經過分析，發(fā)現 “求以求以ak（k=1, 2, 3n）為終點的最長上升子序列的長度）為終點的最長上升子序列的長度”是個是個好的子問題好的子問題這里把一個上升子序列中最右邊的那個數，稱這里把一個上升子序列中最右邊的那個數，稱為該子序列的為該子序列的

23、“終點終點”。雖然這個子問題和原問題形式上并不。雖然這個子問題和原問題形式上并不完全一樣，但是只要這完全一樣，但是只要這n 個子問題都解決了，那么這個子問題都解決了，那么這n 個子問個子問題的解中，最大的那個就是整個問題的解。題的解中，最大的那個就是整個問題的解。n 由上所述的子問題只和一個變量相關，就是數字的位置。因由上所述的子問題只和一個變量相關，就是數字的位置。因此序列中數的位置此序列中數的位置k 就是就是“狀態(tài)狀態(tài)”，而狀態(tài)，而狀態(tài) k 對應的對應的“值值”，就是以就是以ak 做為做為“終點終點”的最長上升子序列的長度。這個問題的最長上升子序列的長度。這個問題的狀態(tài)一共有的狀態(tài)一共有n

24、 個。狀態(tài)定義出來后，轉移方程就不難想了。個。狀態(tài)定義出來后，轉移方程就不難想了。 202、解題思路 n假定假定maxlen (k)表示以表示以ak 做為做為“終點終點”的最長上升子序列的最長上升子序列的長度，那么：的長度，那么：nmaxlen (1) = 1nmaxlen (k) = max maxlen (i)：1i k 且且 ai ak 且且 k1 + 1n這個狀態(tài)轉移方程的意思就是，這個狀態(tài)轉移方程的意思就是，maxlen(k)的值，就是在的值，就是在ak 左邊，左邊，“終點終點”數值小于數值小于ak，且長度最大的那個上升子序列的，且長度最大的那個上升子序列的長度再加長度再加1。因為。

25、因為ak 左邊任何左邊任何“終點終點”小于小于ak 的子序列，加的子序列，加上上ak 后就能形成一個更長的上升子序列。后就能形成一個更長的上升子序列。n實 際 實 現 的 時 候 ， 可 以 不 必 編 寫 遞 歸 函 數 ， 因 為 從實 際 實 現 的 時 候 ， 可 以 不 必 編 寫 遞 歸 函 數 ， 因 為 從 maxlen(1)就能推算出就能推算出maxlen(2)，有了，有了maxlen(1)和和maxlen(2)就能推算出就能推算出maxlen(3)213、參考程序int bmax_n + 10;int amaxlenmax_n + 10;int main(void) int

26、 i, j, n; scanf(%d, & n); for( i = 1;i = n;i + ) scanf(%d, & bi); amaxlen1 = 1;223、參考程序 for( i = 2; i = n; i + ) /求以第求以第i 個數為終點的最長上升子序列的長度個數為終點的最長上升子序列的長度 int ntmp = 0; /記錄第記錄第i 個數左邊子序列最大長度個數左邊子序列最大長度 for( j = 1; j bj ) if( ntmp amaxlenj ) ntmp = amaxlenj; amaxleni = ntmp + 1; int nmax = -1;

27、 for( i = 1;i = n;i + ) if( nmax amaxleni) nmax = amaxleni; printf(%dn, nmax); return 0;思考題：改進此程序，使之思考題：改進此程序，使之能夠輸出最長上升子序列能夠輸出最長上升子序列 23help jimmy 1、問題描述、問題描述 help jimmy 是在下圖所示的場景上完成的游戲：是在下圖所示的場景上完成的游戲：24問題描述 場景中包括多個長度和高度各不相同的平臺。地面是最低場景中包括多個長度和高度各不相同的平臺。地面是最低的平臺，高度為零，長度無限。的平臺，高度為零，長度無限。 jimmy 老鼠在時刻

28、老鼠在時刻0 從高于所有平臺的某處開始下落，它從高于所有平臺的某處開始下落，它的下落速度始終為的下落速度始終為1 米米/秒。當秒。當jimmy 落到某個平臺上時，游落到某個平臺上時，游戲者選擇讓它向左還是向右跑，它跑動的速度也是戲者選擇讓它向左還是向右跑，它跑動的速度也是1 米米/秒。秒。當當jimmy 跑到平臺的邊緣時，開始繼續(xù)下落。跑到平臺的邊緣時，開始繼續(xù)下落。jimmy 每次下每次下落的高度不能超過落的高度不能超過max 米，不然就會摔死，游戲也會結束。米，不然就會摔死，游戲也會結束。 設計一個程序，計算設計一個程序，計算jimmy 到地面時可能的最早時間。到地面時可能的最早時間。25

29、問題描述輸入數據輸入數據n 第一行是測試數據的組數第一行是測試數據的組數t（0 = t = 20）。每組測試數）。每組測試數據的第一行是四個整數據的第一行是四個整數n，x，y，max，用空格分隔。，用空格分隔。n 是是平臺的數目（不包括地面），平臺的數目（不包括地面），x 和和y 是是jimmy 開始下落的位開始下落的位置的橫豎坐標，置的橫豎坐標，max 是一次下落的最大高度。接下來的是一次下落的最大高度。接下來的n 行行每行描述一個平臺，包括三個整數，每行描述一個平臺，包括三個整數，x1i，x2i和和hi。hi表示平臺的高度，表示平臺的高度，x1i和和x2i表示平臺左右端點的橫坐表示平臺左右

30、端點的橫坐標。標。1= n = 1000，-20000 = x, x1i, x2i = 20000，0 hi y = 20000（i = 1.n）。所有坐標）。所有坐標的單位都是米。的單位都是米。n jimmy 的大小和平臺的厚度均忽略不計。如果的大小和平臺的厚度均忽略不計。如果jimmy 恰好恰好落在某個平臺的邊緣，被視為落在平臺上。所有的平臺均不重落在某個平臺的邊緣，被視為落在平臺上。所有的平臺均不重疊或相連。測試數據保疊或相連。測試數據保jimmy 一定能安全到達地面。一定能安全到達地面。26問題描述輸出要求輸出要求對輸入的每組測試數據，輸出一個整數，對輸入的每組測試數據，輸出一個整數，

31、jimmy 到地面時可到地面時可能的最早時間。能的最早時間。輸入樣例輸入樣例13 8 17 200 10 80 10 134 14 3輸出樣例輸出樣例23272、解題思路 n 此題目的此題目的“子問題子問題”是什么呢？是什么呢？n jimmy 跳到一塊板上后，可以有兩種選擇，向左走或向右跳到一塊板上后，可以有兩種選擇，向左走或向右走。走到左端和走到右端所需的時間，容易算出。走。走到左端和走到右端所需的時間，容易算出。n 如果我們能知道，以左端為起點到達地面的最短時間，和以如果我們能知道，以左端為起點到達地面的最短時間，和以右端為起點到達地面的最短時間，那么向左走還是向右走，就右端為起點到達地面

32、的最短時間，那么向左走還是向右走，就很容選擇了。很容選擇了。n 因此，整個問題就被分解成兩個子問題，即因此，整個問題就被分解成兩個子問題，即jimmy 所在位所在位置下方第一塊板左端為起點到地面的最短時間，和右端為起點置下方第一塊板左端為起點到地面的最短時間，和右端為起點到地面的最短時間。這兩個子問題在形式上和原問題是完全一到地面的最短時間。這兩個子問題在形式上和原問題是完全一致的。致的。n 將板子從上到下從將板子從上到下從1 開始進行無重復的編號開始進行無重復的編號(高度相同的板高度相同的板子，哪塊編號在前無所謂子，哪塊編號在前無所謂)，那么，和上面兩個子問題相關的，那么，和上面兩個子問題相

33、關的變量就只有板子的編號。變量就只有板子的編號。282、解題思路 n 所以，本題目的所以，本題目的“狀態(tài)狀態(tài)”就是板子編號，而一個就是板子編號，而一個“狀態(tài)狀態(tài)”對對應的應的“值值”有兩部分，是兩個子問題的解，即從該板子左端出有兩部分，是兩個子問題的解，即從該板子左端出發(fā)到達地面的最短時間，和從該板子右端出發(fā)到達地面的最短發(fā)到達地面的最短時間，和從該板子右端出發(fā)到達地面的最短時間。時間。n 不妨認為不妨認為jimmy 開始的位置是一個編號為開始的位置是一個編號為0，長度為，長度為0 的板的板子，假設子，假設leftmintime(k)表示從表示從k 號板子左端到地面的最短號板子左端到地面的最短

34、時間，時間，rightmintime(k)表示從表示從k 號板子右端到地面的最短號板子右端到地面的最短時間，那么，求板子時間，那么，求板子k 左端點到地面的最短時間的方法如下：左端點到地面的最短時間的方法如下：if ( 板子板子k 左端正下方沒有別的板子左端正下方沒有別的板子) if( 板子板子k 的高度的高度 h(k) 大于大于max) leftmintime(k) = ; else leftmintime(k) = h(k);else if( 板子板子k 左端正下方的板子編號是左端正下方的板子編號是m ) leftmintime(k) = h(k)-h(m) + min(leftminti

35、me(m)+lx(k)-lx(m), rightmintime(m)+rx(m)-lx(k); 292、解題思路 n 上面，上面，h(i)就代表就代表i 號板子的高度，號板子的高度，lx(i)就代表就代表i 號板子左號板子左端點的橫坐標，端點的橫坐標，rx(i)就代表就代表i號板子右端點的橫坐標。那么號板子右端點的橫坐標。那么 h(k)-h(m) 當然就是從當然就是從k 號板子跳到號板子跳到m 號板子所需要的時間，號板子所需要的時間，lx(k)-lx(m) 就是從就是從m 號板子的落腳點走到號板子的落腳點走到m 號板子左端點號板子左端點的時間，的時間，rx(m)-lx(k)就是從就是從m號板子

36、的落腳點走到右端點號板子的落腳點走到右端點所需的時間。所需的時間。n 求求rightmintime(k)的過程類似。的過程類似。n 不妨認為不妨認為jimmy 開始的位置是一個編號為開始的位置是一個編號為0，長度為，長度為0 的板的板子，那么整個問題就是要求子，那么整個問題就是要求leftmintime(0)。n 輸入數據中，板子并沒有按高度排序，所以程序中一定要首輸入數據中，板子并沒有按高度排序，所以程序中一定要首先將板子排序。先將板子排序。303、參考程序#include #include #include #define max_n 1000#define infinite 100000

37、0int t, n, x, y, max;struct platform int lx, rx, h; ;platform aplatformmax_n + 10;int aleftmintimemax_n + 10;int arightmintimemax_n + 10;int mycompare( const void * e1, const void * e2 ) platform * p1, * p2; p1 = (platform * ) e1; p2 = (platform * ) e2; return p2-h - p1-h; /從大到小排列從大到小排列313、參考程序int m

38、intime( int l, bool bleft ) int y = aplatforml.h; int i, x; if( bleft ) x = aplatforml.lx; else x = aplatforml.rx; for( i = l + 1;i = n;i + ) /找到下一張板子找到下一張板子 if( aplatformi.lx = x) break; if( i max )/太高太高 return infinite; 323、參考程序 else /沒找到沒找到 if( y max )/離地面太高離地面太高 return infinite; else return y; /

39、特殊情況處理完畢特殊情況處理完畢 int nlefttime = y - aplatformi.h + x - aplatformi.lx; int nrighttime = y - aplatformi.h + aplatformi.rx - x; if( aleftmintimei = -1 )/還沒有存儲值還沒有存儲值 aleftmintimei = mintime(i, true); if( arightmintimei = -1 ) arightmintimei = mintime(i, false); nlefttime += aleftmintimei; nrighttime +

40、= arightmintimei; if( nlefttime nrighttime ) return nlefttime; return nrighttime;333、參考程序int main(void) scanf(%d, &t); for( int i = 0;i t; i + ) memset(aleftmintime, -1, sizeof(aleftmintime); memset(arightmintime, -1, sizeof(arightmintime); scanf(%d%d%d%d, &n, &x, &y, &max); apla

41、tform0.lx = x; aplatform0.rx = x;/長度為長度為0的板子的板子 aplatform0.h = y; for( int j = 1; j = n; j + ) scanf(%d%d%d, & aplatformj.lx, & aplatformj.rx, & aplatformj.h); qsort(aplatform, n+1, sizeof(platform), mycompare); printf(%dn, mintime(0, true); return 0;思考題：重新編寫此程序，要求不使用遞思考題：重新編寫此程序，要求不使用遞歸

42、函數歸函數34第十課動態(tài)規(guī)劃動態(tài)規(guī)劃( (ii) )綜合實踐考核35最長公共子序列 1、問題描述、問題描述 我們稱序列我們稱序列z = 是序列是序列x = 的子序列當且僅當存在嚴格上升的序列的子序列當且僅當存在嚴格上升的序列，使得對使得對j = 1, 2, . ,k, 有有xij = zj。比如。比如z = 是是x = 的子序列。的子序列?，F在給出兩個序列現在給出兩個序列x 和和y，你的任務是找到，你的任務是找到x 和和y 的最大公共的最大公共子序列，也就是說要找到一個最長的序列子序列，也就是說要找到一個最長的序列z，使得，使得z 既是既是x 的的子序列也是子序列也是y 的子序列。的子序列。輸

43、入數據輸入數據輸入包括多組測試數據。每組數據包括一行，給出兩個長度不輸入包括多組測試數據。每組數據包括一行，給出兩個長度不超過超過200 的字符串，表示兩個序列。兩個字符串之間由若干的字符串，表示兩個序列。兩個字符串之間由若干個空格隔開。個空格隔開。36問題描述 輸出要求輸出要求 對每組輸入數據，輸出一行，給出兩個序列的最大公共子序對每組輸入數據，輸出一行，給出兩個序列的最大公共子序列的長度。列的長度。 輸入樣例輸入樣例 abcfbc abfcab programming contest abcd mnp 輸出樣例輸出樣例 4 2 0372、解題思路 n用字符數組用字符數組s1、s2存放兩個字

44、符串，用存放兩個字符串，用s1i表示表示s1中的第中的第i 個字符，個字符，s2j表示表示s2中的第中的第j個字符（字符編號從個字符（字符編號從1 開始），開始），用用s1i表示表示s1的前的前i個字符所構成的子串，個字符所構成的子串，s2j表示表示s2的前的前j個字個字符構成的子串，符構成的子串，maxlen(i,j)表示表示s1i 和和s2j 的最長公共子序列的最長公共子序列的長度，那么遞推關系如下：的長度，那么遞推關系如下：nif( i =0 | j = 0 ) n maxlen(i, j) = 0 /兩個空串的最長公共子序列長度是兩個空串的最長公共子序列長度是0nelse if( s1

45、i = s2j )n maxlen(i, j) = maxlen(i-1, j-1 ) + 1;nelse n maxlen(i,j) = max(maxlen(i, j-1), maxlen(i-1, j);382、解題思路 n 顯然本題目的顯然本題目的“狀態(tài)狀態(tài)”就是就是s1 中的位置中的位置i 和和s2 中的位置中的位置j。n “值值”就是就是maxlen(i, j)。n 狀態(tài)的數目是狀態(tài)的數目是s1 長度和長度和s2 長度的乘積?？砷L度的乘積?？梢杂靡粋€二維數組來存儲各個狀態(tài)下的以用一個二維數組來存儲各個狀態(tài)下的“值值”。n 本問題的兩個子問題，和原問題形式完全一本問題的兩個子問題，和

46、原問題形式完全一致的，只不過規(guī)模小了一點。致的，只不過規(guī)模小了一點。393、參考程序#include #include #define max_len 1000char sz1max_len;char sz2max_len;int amaxlenmax_lenmax_len;int main(void) while( scanf(%s%s, sz1+1 ,sz2+1 ) 0 ) int nlength1 = strlen( sz1+1); int nlength2 = strlen( sz2+1); int i, j; for( i = 0;i = nlength1; i + ) amaxle

47、ni0 = 0; for( j = 0;j = nlength2; j + ) amaxlen0j = 0;403、參考程序 for( i = 1;i = nlength1;i + ) for( j = 1; j nlen2 ) amaxlenij = nlen1; else amaxlenij = nlen2; printf(%dn, amaxlennlength1nlength2); return 0;41陪審團的人選 1、問題描述、問題描述 在遙遠的國家佛羅布尼亞，嫌犯是否有罪，須由陪審團決在遙遠的國家佛羅布尼亞，嫌犯是否有罪，須由陪審團決定。陪審團是由法官從公眾中挑選的。先隨機挑選定。

48、陪審團是由法官從公眾中挑選的。先隨機挑選n 個人作為個人作為陪審團的候選人，然后再從這陪審團的候選人，然后再從這n 個人中選個人中選m 人組成陪審團。人組成陪審團。選選m 人的辦法是：人的辦法是： 控方和辯方會根據對候選人的喜歡程度，給所有候選人打控方和辯方會根據對候選人的喜歡程度，給所有候選人打分，分值從分，分值從0 到到20。為了公平起見，法官選出陪審團的原則。為了公平起見，法官選出陪審團的原則是：選出的是：選出的m 個人，必須滿足辯方總分和控方總分的差的絕個人，必須滿足辯方總分和控方總分的差的絕對值最小。如果有多種選擇方案的辯方總分和控方總分的之差對值最小。如果有多種選擇方案的辯方總分和

49、控方總分的之差的絕對值相同，那么選辯控雙方總分之和最大的方案即可。最的絕對值相同，那么選辯控雙方總分之和最大的方案即可。最終選出的方案稱為陪審團方案。終選出的方案稱為陪審團方案。42問題描述輸入數據輸入數據輸入包含多組數據。每組數據的第一行是兩個整數輸入包含多組數據。每組數據的第一行是兩個整數n 和和m，n 是候選人數目，是候選人數目，m 是陪審團人數。注意，是陪審團人數。注意，1=n=200, 1=m=20 而且而且 m=n。接下來的。接下來的n 行，每行表示一個候行，每行表示一個候選人的信息，它包含選人的信息，它包含2 個整數，先后是控方和辯方對該候選人個整數，先后是控方和辯方對該候選人的

50、打分。候選人按出現的先后從的打分。候選人按出現的先后從1開始編號。兩組有效數據之開始編號。兩組有效數據之間以空行分隔。最后一組數據間以空行分隔。最后一組數據n=m=0輸出要求輸出要求對每組數據，先輸出一行，表示答案所屬的組號對每組數據，先輸出一行，表示答案所屬的組號, 如如 jury #1, jury #2, 等。接下來的一行要象例子那樣輸出陪審團等。接下來的一行要象例子那樣輸出陪審團的控方總分和辯方總分。再下來一行要以升序輸出陪審團里每的控方總分和辯方總分。再下來一行要以升序輸出陪審團里每個成員的編號，兩個成員編號之間用空格分隔。每組輸出數據個成員的編號，兩個成員編號之間用空格分隔。每組輸出

51、數據須以一個空行結束。須以一個空行結束。43問題描述輸入樣例輸入樣例4 21 22 34 16 20 0輸出樣例輸出樣例jury #1best jury has value 6 for prosecution and value 4 for defence:2 3442、解題思路 n為敘述方便，將任一選擇方案中，辯方總分和控方總分之差為敘述方便，將任一選擇方案中，辯方總分和控方總分之差簡稱為簡稱為“辯控差辯控差”，辯方總分和控方總分之和稱為，辯方總分和控方總分之和稱為“辯控和辯控和”。n第第i 個候選人的辯方總分和控方總分之差記為個候選人的辯方總分和控方總分之差記為v(i)，辯方總分，辯方總分

52、和控方總分之和記為和控方總分之和記為s(i)。n現用現用f(j, k)表示，取表示，取j 個候選人，使其辯控差為個候選人，使其辯控差為k 的所有方案的所有方案中，辯控和最大的那個方案（該方案稱為中，辯控和最大的那個方案（該方案稱為“方案方案f(j, k)”）的）的辯控和。辯控和。并且，我們還規(guī)定，如果沒法選并且，我們還規(guī)定，如果沒法選j 個人，使其辯控差個人，使其辯控差為為k，那么，那么f(j, k)的值就為的值就為-1，也稱方案，也稱方案f(j, k)不可行。不可行。n本題是要求選出本題是要求選出m 個人，那么，如果對個人，那么，如果對k 的所有可能的取值，的所有可能的取值，求出了所有的求出

53、了所有的f(m, k) (-20m k 20m)，那么陪審團，那么陪審團方案自然就很容易找到了。方案自然就很容易找到了。452、解題思路 n問題的關鍵是建立遞推關系。顯然，方案問題的關鍵是建立遞推關系。顯然，方案f(j, k)是由某個可是由某個可行的方案行的方案f(j-1, x)( -20m x 20m)演化而來的。演化而來的。n可行方案可行方案f(j-1, x)能演化成方案能演化成方案f(j, k)的必要條件是：存在的必要條件是：存在某個候選人某個候選人i，i 在方案在方案f(j-1, x)中沒有被選上，且中沒有被選上，且x+v(i) = k。在所有滿足該必要條件的在所有滿足該必要條件的f(

54、j-1, x)中，選出中，選出 f(j-1, x) + s(i) 的值最大的那個，那么方案的值最大的那個，那么方案f(j-1, x)再加上候選人再加上候選人i，就演變，就演變成了方案成了方案 f(j, k)。n由上面知一個方案都選了哪些人需要全部記錄下來。不妨由上面知一個方案都選了哪些人需要全部記錄下來。不妨將將方案方案f(j, k)中最后選的那個候選人的編號，記在二維數組的元中最后選的那個候選人的編號，記在二維數組的元素素pathjk中中。那么方案。那么方案f(j, k)的倒數第二個人選的編號，的倒數第二個人選的編號，就是就是pathj-1k-vpathjk。n假定最后算出了方案的辯控差是假

55、定最后算出了方案的辯控差是k，那么從，那么從pathmk出發(fā)，出發(fā)，就能順藤摸瓜一步步求出所有被選中的候選人。就能順藤摸瓜一步步求出所有被選中的候選人。462、解題思路 n初始條件，只能確定初始條件，只能確定f(0, 0) = 0。由此出發(fā)，一步步自底向。由此出發(fā)，一步步自底向上遞推，就能求出所有的可行方案上遞推，就能求出所有的可行方案f(m, k)( -20m k 20m)。n實際解題的時候，會用一個二維數組實際解題的時候，會用一個二維數組f 來存放來存放f(j, k)的值。而的值。而且，由于題目中辯控差的值且，由于題目中辯控差的值k 可以為負數，而程序中數租下標可以為負數，而程序中數租下標

56、不能為負數，所以，在程序中不妨將辯控差的值都加上不能為負數，所以，在程序中不妨將辯控差的值都加上20m，以免下標為負數導致出錯，即題目描述中，如果辯，以免下標為負數導致出錯，即題目描述中，如果辯控差為控差為0，則在程序中辯控差為，則在程序中辯控差為20m。473、參考程序#include #include #include int f301000;int path301000;int p300; /控方打分控方打分int d300; /辯方打分辯方打分int answer30; /存放最終方案的人選存放最終方案的人選int compareint(const void * e1, const v

57、oid * e2) return * (int *) e1) - * (int *) e2);483、參考程序int main(void) int i, j, k; int t1, t2; int n, m; int nminp_d; /辯控雙方總分一樣時的辯控差辯控雙方總分一樣時的辯控差 int ncaseno;/測試數據編號測試數據編號 ncaseno=0; scanf(%d%d, &n, &m); while(n+m) ncaseno+; for(i=1;i=n;i+) scanf(%d%d, &pi, &di); memset(f, -1, sizeof

58、(f); memset(path, 0, sizeof(path); nminp_d=m*20; /題目中的辯控差為題目中的辯控差為0 /對應到程序中辯控差就是對應到程序中辯控差就是m*20 f0nminp_d=0; /選選0 個人辯控差為個人辯控差為0 的方案，其辯控和就是的方案，其辯控和就是0493、參考程序 for(j=0;jm;j+) /每次循環(huán)選出第每次循環(huán)選出第j 個人，共要選出個人，共要選出m 人人 for(k=0;k=0) /方案方案 f(j, k)可行可行 for(i=1;ifj+1k+pi-di) /即時判別記住更合適的即時判別記住更合適的f(j,k) t1=j; t2=k

59、; while(t10&patht1t2!=i) /t2減去編號為減去編號為patht1t2的辯控差的辯控差 t2-=ppatht1t2-dpatht1t2; t1-;/減少減少1人人 if(t1=0) /沒有發(fā)現沒有發(fā)現 fj+1k+pi-di=fjk+pi+di; pathj+1k+pi-di=i; 503、參考程序 i=nminp_d; j=0; while(fmi+j0&fmi-jfmi-j)/絕對值相同時找辯控和最大的絕對值相同時找辯控和最大的 k=i+j; else k=i-j; printf(jury #%dn, ncaseno); printf(best jur

60、y has value %d for prosecution and value %d for defence:n, (k-nminp_d+fmk)/2, (fmk-k+nminp_d)/2); for(i=1;i=m;i+) answeri=pathm-i+1k; k-=pansweri-dansweri;/減去辯控差減去辯控差 qsort(answer+1, m, sizeof(int), compareint); for(i=1;i=m;i+) printf( %d, answeri); printf(n); printf(n); scanf(%d%d, &n, &m); return 0;51購物問題 1、問題描述、問題描述 由于換季，由于換季，acm商場推出優(yōu)惠活動，以超低價格出售商場推出優(yōu)惠活動，以超低價格出售若干種商品。但是，商場為避