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

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

3、1 開始算開始算)，以，以MaxSum(r, j) 代表從第代表從第 r 行的第行的第 j 個數(shù)字到底邊的最佳路徑個數(shù)字到底邊的最佳路徑的數(shù)字之和，則本題是要求的數(shù)字之和，則本題是要求 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) +

4、 D(r, j)。所。所以，選擇往哪里走，就看以，選擇往哪里走，就看MaxSum(r+1, j)和和MaxSum(r+1, j+1)哪個更大了。哪個更大了。3、參考程序 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+

5、Drj; 3、參考程序 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;提交結(jié)果：提交結(jié)果：Time Limit Exceed程序I分析 上面的程序，效率非常低，在上面的程序，效率非常低，在N 值并不大，值并不大，比如比如N=100 的時候，就慢得幾乎永遠(yuǎn)算不出的時候，就慢得幾乎永遠(yuǎn)算不出結(jié)果了。結(jié)果了。為什么會這樣呢？是因為過多的重復(fù)計算。為什么會這樣呢？是因為過

6、多的重復(fù)計算。我們不妨將對我們不妨將對MaxSum 函數(shù)的一次調(diào)用稱為函數(shù)的一次調(diào)用稱為一次計算。那么，每次計算一次計算。那么，每次計算MaxSum(r, j)的的時候，都要計算一次時候，都要計算一次MaxSum(r+1, j+1)，而每次計算而每次計算MaxSum(r, j+1)的時候，也要的時候，也要計算一次計算一次MaxSum(r+1, j+1)。重復(fù)計算因。重復(fù)計算因此產(chǎn)生。此產(chǎn)生。在 題 目 中 給 出 的 例 子 里 ， 如 果 我 們 將在 題 目 中 給 出 的 例 子 里 ， 如 果 我 們 將MaxSum(r, j)被計算的次數(shù)都寫在位置（被計算的次數(shù)都寫在位置（r, j）

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

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

9、的次數(shù)）就是三角形中的數(shù)字總數(shù)，即次數(shù)）就是三角形中的數(shù)字總數(shù)，即1+2+3+N = N(N+1)/2。n 如何存放計算出來的如何存放計算出來的MaxSum（r, j）值呢？顯然，用一個二維）值呢？顯然，用一個二維數(shù)組數(shù)組aMaxSumNN就能解決。就能解決。aMaxSumrj就存放就存放MaxSum(r, j)的計算結(jié)果。下次再需要的計算結(jié)果。下次再需要MaxSum(r, j)的值時，的值時，不必再調(diào)用不必再調(diào)用MaxSum 函數(shù)，只需直接取函數(shù)，只需直接取aMaxSumrj的值即的值即可。可。4、參考程序 II#include #include #define MAX_NUM 100int

10、 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 ) return a

11、MaxSumr+1j +Drj; return aMaxSumr+1j+1 + Drj;4、參考程序 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(1, 1); return 0;程序

12、II分析 這種將一個問題分解為子問題遞歸求解，并且將中間結(jié)果這種將一個問題分解為子問題遞歸求解，并且將中間結(jié)果保存以避免重復(fù)計算的辦法，就叫做保存以避免重復(fù)計算的辦法，就叫做“動態(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)的。以上題為例，以上題為例，最佳路徑上面的每個數(shù)字到底部的那一段路徑，都是從該數(shù)最佳路徑上面的每個數(shù)字到底部的那一段路徑，都是從該數(shù)字出發(fā)到達(dá)到底部的最佳路徑。字出發(fā)到達(dá)到底部的最佳路徑。實際上，遞歸的思想在

13、編程時未必要實現(xiàn)為遞歸函數(shù)。在上實際上，遞歸的思想在編程時未必要實現(xiàn)為遞歸函數(shù)。在上面的例子里，有遞推公式：面的例子里，有遞推公式： Drj rNaMaxSumrjMax(aMaxSumr1j, aMaxSumr1j1)Drj 其其他他因此，不需要寫遞歸函數(shù)，從因此，不需要寫遞歸函數(shù)，從aMaxSumN-1這一行元素這一行元素開始向上逐行遞推，就能求得開始向上逐行遞推，就能求得aMaxSum11的值了。的值了。5、參考程序 IIIint DMAX_NUM + 10MAX_NUM + 10;int N;int aMaxSumMAX_NUM + 10MAX_NUM + 10;int main(vo

14、id) 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;思考題思考題：上面的幾個程序：上面的幾個程序只算出了最佳路徑的數(shù)字只算出了最佳路徑的數(shù)字之和

15、。如果要求輸出最佳之和。如果要求輸出最佳路徑上的每個數(shù)字，該怎路徑上的每個數(shù)字，該怎么辦？么辦？動態(tài)規(guī)劃解題的一般思路 n 許多求最優(yōu)解的問題可以用動態(tài)規(guī)劃來解決。許多求最優(yōu)解的問題可以用動態(tài)規(guī)劃來解決。n 首先要把原問題分解為若干個子問題。注意單純的遞歸往往會導(dǎo)首先要把原問題分解為若干個子問題。注意單純的遞歸往往會導(dǎo)致子問題被重復(fù)計算，用動態(tài)規(guī)劃的方法，子問題的解一旦求出就致子問題被重復(fù)計算，用動態(tài)規(guī)劃的方法，子問題的解一旦求出就要被保存，所以每個子問題只需求解一次。要被保存，所以每個子問題只需求解一次。 n 子問題經(jīng)常和原問題形式相似，有時甚至完全一樣，只不過規(guī)模子問題經(jīng)常和原問題形式相似

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

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

18、的最大和底邊路徑的最大和”。這個子問題和兩個變量。這個子問題和兩個變量r 和和j 相關(guān)，那相關(guān)，那么一個么一個“狀態(tài)狀態(tài)”，就是，就是r, j 的一組取值，即每個數(shù)字的位置就的一組取值，即每個數(shù)字的位置就是一個是一個“狀態(tài)狀態(tài)”。該。該“狀態(tài)狀態(tài)”所對應(yīng)的所對應(yīng)的“值值”，就是從該位置，就是從該位置的數(shù)字開始，到底邊的最佳路徑上的數(shù)字之和。的數(shù)字開始，到底邊的最佳路徑上的數(shù)字之和。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)轉(zhuǎn)移方程轉(zhuǎn)移方程”。動態(tài)規(guī)劃解題的一般思路 n用動態(tài)規(guī)劃解題，如何尋找用動態(tài)規(guī)劃解題，如何尋找“子問題子問題”，定義，定義“狀態(tài)狀態(tài)”，“狀態(tài)轉(zhuǎn)移方程狀態(tài)轉(zhuǎn)移方程”是什么樣的，并沒有一定之規(guī)，需要具體問是什么樣的，并沒有一定之規(guī)，需要具體問題具體分析，題目做多了就會有感覺。題具體分析，題目做多了就會有感覺。n甚至，對于同一個問題，分解成子問題的辦法可能不止一種，甚至，對于同一個問題，分解成子問題的辦法可能不止一種，因而因而

20、“狀態(tài)狀態(tài)”也可以有不同的定義方法。不同的也可以有不同的定義方法。不同的“狀態(tài)狀態(tài)”定義定義方法可能會導(dǎo)致時間、空間效率上的區(qū)別。方法可能會導(dǎo)致時間、空間效率上的區(qū)別。 Drj rNaMaxSumrjMax(aMaxSumr1j, aMaxSumr1j1)Drj 其其他他最長上升子序列 1、問題描述、問題描述 一個數(shù)的序列一個數(shù)的序列bi，當(dāng)，當(dāng)b1 b2 . bS 的時候，的時候，我們稱這個序列是上升的。對于給定的一個序列我們稱這個序列是上升的。對于給定的一個序列(a1, a2, ., aN)，我們可以得到一些上升的子序列，我們可以得到一些上升的子序列(ai1, ai2, ., aiK)，這

21、里，這里1 = i1 i2 . iK = N。比如，對于序列比如，對于序列(1, 7, 3, 5, 9, 4, 8)，有它的一些上，有它的一些上升子序列，如升子序列，如(1, 7), (3, 4, 8)等等。這些子序列中等等。這些子序列中最長的長度是最長的長度是4，比如子序列，比如子序列(1, 3, 5, 8).你的任務(wù)，就是對于給定的序列，求出最長上升子序你的任務(wù)，就是對于給定的序列，求出最長上升子序列的長度。列的長度。問題描述輸入數(shù)據(jù)輸入數(shù)據(jù)輸入的第一行是序列的長度輸入的第一行是序列的長度N (1 = N = 1000)。第二行。第二行給出序列中的給出序列中的N 個整數(shù)，這些整數(shù)的取值范圍

22、都在個整數(shù)，這些整數(shù)的取值范圍都在0 到到10000。輸出要求輸出要求最長上升子序列的長度。最長上升子序列的長度。輸入樣例輸入樣例71 7 3 5 9 4 8輸出樣例輸出樣例42、解題思路 n 如何把這個問題分解成子問題呢？經(jīng)過分析，發(fā)現(xiàn)如何把這個問題分解成子問題呢？經(jīng)過分析，發(fā)現(xiàn) “求以求以ak（k=1, 2, 3N）為終點(diǎn)的最長上升子序列的長度）為終點(diǎn)的最長上升子序列的長度”是個是個好的子問題好的子問題這里把一個上升子序列中最右邊的那個數(shù)，稱這里把一個上升子序列中最右邊的那個數(shù)，稱為該子序列的為該子序列的“終點(diǎn)終點(diǎn)”。雖然這個子問題和原問題形式上并不。雖然這個子問題和原問題形式上并不完全一

23、樣，但是只要這完全一樣，但是只要這N 個子問題都解決了，那么這個子問題都解決了，那么這N 個子問個子問題的解中，最大的那個就是整個問題的解。題的解中，最大的那個就是整個問題的解。n 由上所述的子問題只和一個變量相關(guān)，就是數(shù)字的位置。因由上所述的子問題只和一個變量相關(guān)，就是數(shù)字的位置。因此序列中數(shù)的位置此序列中數(shù)的位置k 就是就是“狀態(tài)狀態(tài)”，而狀態(tài)，而狀態(tài) k 對應(yīng)的對應(yīng)的“值值”，就是以就是以ak 做為做為“終點(diǎn)終點(diǎn)”的最長上升子序列的長度。這個問題的最長上升子序列的長度。這個問題的狀態(tài)一共有的狀態(tài)一共有N 個。狀態(tài)定義出來后，轉(zhuǎn)移方程就不難想了。個。狀態(tài)定義出來后，轉(zhuǎn)移方程就不難想了。 2

24、、解題思路 n假定假定MaxLen (k)表示以表示以ak 做為做為“終點(diǎn)終點(diǎn)”的最長上升子序列的最長上升子序列的長度，那么：的長度，那么：nMaxLen (1) = 1nMaxLen (k) = Max MaxLen (i)：1i k 且且 ai ak 且且 k1 + 1n這個狀態(tài)轉(zhuǎn)移方程的意思就是，這個狀態(tài)轉(zhuǎn)移方程的意思就是，MaxLen(k)的值，就是在的值，就是在ak 左邊，左邊，“終點(diǎn)終點(diǎn)”數(shù)值小于數(shù)值小于ak，且長度最大的那個上升子序列的，且長度最大的那個上升子序列的長度再加長度再加1。因為。因為ak 左邊任何左邊任何“終點(diǎn)終點(diǎn)”小于小于ak 的子序列，加的子序列，加上上ak 后就

25、能形成一個更長的上升子序列。后就能形成一個更長的上升子序列。n實 際 實 現(xiàn) 的 時 候 ， 可 以 不 必 編 寫 遞 歸 函 數(shù) ， 因 為 從實 際 實 現(xiàn) 的 時 候 ， 可 以 不 必 編 寫 遞 歸 函 數(shù) ， 因 為 從 MaxLen(1)就能推算出就能推算出MaxLen(2)，有了，有了MaxLen(1)和和MaxLen(2)就能推算出就能推算出MaxLen(3)3、參考程序int bMAX_N + 10;int aMaxLenMAX_N + 10;int main(void) int i, j, N; scanf(%d, & N); for( i = 1;i = N;i +

26、) scanf(%d, & bi); aMaxLen1 = 1;3、參考程序 for( i = 2; i = N; i + ) /求以第求以第i 個數(shù)為終點(diǎn)的最長上升子序列的長度個數(shù)為終點(diǎn)的最長上升子序列的長度 int nTmp = 0; /記錄第記錄第i 個數(shù)左邊子序列最大長度個數(shù)左邊子序列最大長度 for( j = 1; j bj ) if( nTmp aMaxLenj ) nTmp = aMaxLenj; aMaxLeni = nTmp + 1; int nMax = -1; for( i = 1;i = N;i + ) if( nMax aMaxLeni) nMax = aMaxLen

27、i; printf(%dn, nMax); return 0;思考題：改進(jìn)此程序，使之思考題：改進(jìn)此程序，使之能夠輸出最長上升子序列能夠輸出最長上升子序列 Help Jimmy 1、問題描述、問題描述 Help Jimmy 是在下圖所示的場景上完成的游戲：是在下圖所示的場景上完成的游戲：問題描述 場景中包括多個長度和高度各不相同的平臺。地面是最低場景中包括多個長度和高度各不相同的平臺。地面是最低的平臺，高度為零，長度無限。的平臺，高度為零，長度無限。 Jimmy 老鼠在時刻老鼠在時刻0 從高于所有平臺的某處開始下落，它從高于所有平臺的某處開始下落，它的下落速度始終為的下落速度始終為1 米米/秒

28、。當(dāng)秒。當(dāng)Jimmy 落到某個平臺上時，游落到某個平臺上時，游戲者選擇讓它向左還是向右跑，它跑動的速度也是戲者選擇讓它向左還是向右跑，它跑動的速度也是1 米米/秒。秒。當(dāng)當(dāng)Jimmy 跑到平臺的邊緣時，開始繼續(xù)下落。跑到平臺的邊緣時，開始繼續(xù)下落。Jimmy 每次下每次下落的高度不能超過落的高度不能超過MAX 米，不然就會摔死，游戲也會結(jié)束。米，不然就會摔死，游戲也會結(jié)束。 設(shè)計一個程序，計算設(shè)計一個程序，計算Jimmy 到地面時可能的最早時間。到地面時可能的最早時間。問題描述輸入數(shù)據(jù)輸入數(shù)據(jù)n 第一行是測試數(shù)據(jù)的組數(shù)第一行是測試數(shù)據(jù)的組數(shù)t（0 = t = 20）。每組測試數(shù)）。每組測試數(shù)據(jù)

29、的第一行是四個整數(shù)據(jù)的第一行是四個整數(shù)N，X，Y，MAX，用空格分隔。，用空格分隔。N 是是平臺的數(shù)目（不包括地面），平臺的數(shù)目（不包括地面），X 和和Y 是是Jimmy 開始下落的位開始下落的位置的橫豎坐標(biāo)，置的橫豎坐標(biāo)，MAX 是一次下落的最大高度。接下來的是一次下落的最大高度。接下來的N 行行每行描述一個平臺，包括三個整數(shù)，每行描述一個平臺，包括三個整數(shù)，X1i，X2i和和Hi。Hi表示平臺的高度，表示平臺的高度，X1i和和X2i表示平臺左右端點(diǎn)的橫坐表示平臺左右端點(diǎn)的橫坐標(biāo)。標(biāo)。1= N = 1000，-20000 = X, X1i, X2i = 20000，0 Hi Y = 2000

30、0（i = 1.N）。所有坐標(biāo)）。所有坐標(biāo)的單位都是米。的單位都是米。n Jimmy 的大小和平臺的厚度均忽略不計。如果的大小和平臺的厚度均忽略不計。如果Jimmy 恰好恰好落在某個平臺的邊緣，被視為落在平臺上。所有的平臺均不重落在某個平臺的邊緣，被視為落在平臺上。所有的平臺均不重疊或相連。測試數(shù)據(jù)保疊或相連。測試數(shù)據(jù)保Jimmy 一定能安全到達(dá)地面。一定能安全到達(dá)地面。問題描述輸出要求輸出要求對輸入的每組測試數(shù)據(jù)，輸出一個整數(shù)，對輸入的每組測試數(shù)據(jù)，輸出一個整數(shù)，Jimmy 到地面時可到地面時可能的最早時間。能的最早時間。輸入樣例輸入樣例13 8 17 200 10 80 10 134 14

31、 3輸出樣例輸出樣例232、解題思路 n 此題目的此題目的“子問題子問題”是什么呢？是什么呢？n Jimmy 跳到一塊板上后，可以有兩種選擇，向左走或向右跳到一塊板上后，可以有兩種選擇，向左走或向右走。走到左端和走到右端所需的時間，容易算出。走。走到左端和走到右端所需的時間，容易算出。n 如果我們能知道，以左端為起點(diǎn)到達(dá)地面的最短時間，和以如果我們能知道，以左端為起點(diǎn)到達(dá)地面的最短時間，和以右端為起點(diǎn)到達(dá)地面的最短時間，那么向左走還是向右走，就右端為起點(diǎn)到達(dá)地面的最短時間，那么向左走還是向右走，就很容選擇了。很容選擇了。n 因此，整個問題就被分解成兩個子問題，即因此，整個問題就被分解成兩個子問

32、題，即Jimmy 所在位所在位置下方第一塊板左端為起點(diǎn)到地面的最短時間，和右端為起點(diǎn)置下方第一塊板左端為起點(diǎn)到地面的最短時間，和右端為起點(diǎn)到地面的最短時間。這兩個子問題在形式上和原問題是完全一到地面的最短時間。這兩個子問題在形式上和原問題是完全一致的。致的。n 將板子從上到下從將板子從上到下從1 開始進(jìn)行無重復(fù)的編號開始進(jìn)行無重復(fù)的編號(高度相同的板高度相同的板子，哪塊編號在前無所謂子，哪塊編號在前無所謂)，那么，和上面兩個子問題相關(guān)的，那么，和上面兩個子問題相關(guān)的變量就只有板子的編號。變量就只有板子的編號。2、解題思路 n 所以，本題目的所以，本題目的“狀態(tài)狀態(tài)”就是板子編號，而一個就是板子

33、編號，而一個“狀態(tài)狀態(tài)”對對應(yīng)的應(yīng)的“值值”有兩部分，是兩個子問題的解，即從該板子左端出有兩部分，是兩個子問題的解，即從該板子左端出發(fā)到達(dá)地面的最短時間，和從該板子右端出發(fā)到達(dá)地面的最短發(fā)到達(dá)地面的最短時間，和從該板子右端出發(fā)到達(dá)地面的最短時間。時間。n 不妨認(rèn)為不妨認(rèn)為Jimmy 開始的位置是一個編號為開始的位置是一個編號為0，長度為，長度為0 的板的板子，假設(shè)子，假設(shè)LeftMinTime(k)表示從表示從k 號板子左端到地面的最短號板子左端到地面的最短時間，時間，RightMinTime(k)表示從表示從k 號板子右端到地面的最短號板子右端到地面的最短時間，那么，求板子時間，那么，求板子

34、k 左端點(diǎn)到地面的最短時間的方法如下：左端點(diǎn)到地面的最短時間的方法如下：if ( 板子板子k 左端正下方?jīng)]有別的板子左端正下方?jīng)]有別的板子) if( 板子板子k 的高度的高度 h(k) 大于大于Max) LeftMinTime(k) = ; else LeftMinTime(k) = h(k);else if( 板子板子k 左端正下方的板子編號是左端正下方的板子編號是m ) LeftMinTime(k) = h(k)-h(m) + Min(LeftMinTime(m)+Lx(k)-Lx(m), RightMinTime(m)+Rx(m)-Lx(k); 2、解題思路 n 上面，上面，h(i)就代

35、表就代表i 號板子的高度，號板子的高度，Lx(i)就代表就代表i 號板子左號板子左端點(diǎn)的橫坐標(biāo)，端點(diǎn)的橫坐標(biāo)，Rx(i)就代表就代表i號板子右端點(diǎn)的橫坐標(biāo)。那么號板子右端點(diǎn)的橫坐標(biāo)。那么 h(k)-h(m) 當(dāng)然就是從當(dāng)然就是從k 號板子跳到號板子跳到m 號板子所需要的時間，號板子所需要的時間，Lx(k)-Lx(m) 就是從就是從m 號板子的落腳點(diǎn)走到號板子的落腳點(diǎn)走到m 號板子左端點(diǎn)號板子左端點(diǎn)的時間，的時間，Rx(m)-Lx(k)就是從就是從m號板子的落腳點(diǎn)走到右端點(diǎn)號板子的落腳點(diǎn)走到右端點(diǎn)所需的時間。所需的時間。n 求求RightMinTime(k)的過程類似。的過程類似。n 不妨認(rèn)為不

36、妨認(rèn)為Jimmy 開始的位置是一個編號為開始的位置是一個編號為0，長度為，長度為0 的板的板子，那么整個問題就是要求子，那么整個問題就是要求LeftMinTime(0)。n 輸入數(shù)據(jù)中，板子并沒有按高度排序，所以程序中一定要首輸入數(shù)據(jù)中，板子并沒有按高度排序，所以程序中一定要首先將板子排序。先將板子排序。3、參考程序#include #include #include #define MAX_N 1000#define INFINITE 1000000int t, n, x, y, max;struct Platform int Lx, Rx, h; ;Platform aPlatformMA

37、X_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; /從大到小排列從大到小排列3、參考程序int MinTime( int L, bool bLeft ) int y = aPlatformL.h; int i, x; if( bLeft ) x =

38、 aPlatformL.Lx; else x = aPlatformL.Rx; for( i = L + 1;i = n;i + ) /找到下一張板子找到下一張板子 if( aPlatformi.Lx = x) break; if( i max )/太高太高 return INFINITE; 3、參考程序 else /沒找到?jīng)]找到 if( y max )/離地面太高離地面太高 return INFINITE; else return y; /特殊情況處理完畢特殊情況處理完畢 int nLeftTime = y - aPlatformi.h + x - aPlatformi.Lx; int nR

39、ightTime = y - aPlatformi.h + aPlatformi.Rx - x; if( aLeftMinTimei = -1 )/還沒有存儲值還沒有存儲值 aLeftMinTimei = MinTime(i, true); if( aRightMinTimei = -1 ) aRightMinTimei = MinTime(i, false); nLeftTime += aLeftMinTimei; nRightTime += aRightMinTimei; if( nLeftTime nRightTime ) return nLeftTime; return nRightT

40、ime;3、參考程序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); aPlatform0.Lx = x; aPlatform0.Rx = x;/長度為長度為0的板子的板子 aPlatform0.h = y; for( int j = 1; j = n; j + ) scan

41、f(%d%d%d, & aPlatformj.Lx, & aPlatformj.Rx, & aPlatformj.h); qsort(aPlatform, n+1, sizeof(Platform), MyCompare); printf(%dn, MinTime(0, true); return 0;思考題：重新編寫此程序，要求不使用遞思考題：重新編寫此程序，要求不使用遞歸函數(shù)歸函數(shù)2022-6-2734第十課動態(tài)規(guī)劃動態(tài)規(guī)劃( (II) )綜合實踐考核最長公共子序列 1、問題描述、問題描述 我們稱序列我們稱序列Z = 是序列是序列X = 的子序列當(dāng)且僅當(dāng)存在嚴(yán)格上升的序列的子序列當(dāng)且僅當(dāng)存

42、在嚴(yán)格上升的序列，使得對使得對j = 1, 2, . ,k, 有有xij = zj。比如。比如Z = 是是X = 的子序列。的子序列。現(xiàn)在給出兩個序列現(xiàn)在給出兩個序列X 和和Y，你的任務(wù)是找到，你的任務(wù)是找到X 和和Y 的最大公共的最大公共子序列，也就是說要找到一個最長的序列子序列，也就是說要找到一個最長的序列Z，使得，使得Z 既是既是X 的的子序列也是子序列也是Y 的子序列。的子序列。輸入數(shù)據(jù)輸入數(shù)據(jù)輸入包括多組測試數(shù)據(jù)。每組數(shù)據(jù)包括一行，給出兩個長度不輸入包括多組測試數(shù)據(jù)。每組數(shù)據(jù)包括一行，給出兩個長度不超過超過200 的字符串，表示兩個序列。兩個字符串之間由若干的字符串，表示兩個序列。兩

43、個字符串之間由若干個空格隔開。個空格隔開。問題描述 輸出要求輸出要求 對每組輸入數(shù)據(jù)，輸出一行，給出兩個序列的最大公共子序?qū)γ拷M輸入數(shù)據(jù)，輸出一行，給出兩個序列的最大公共子序列的長度。列的長度。 輸入樣例輸入樣例 abcfbc abfcab programming contest abcd mnp 輸出樣例輸出樣例 4 2 02、解題思路 n用字符數(shù)組用字符數(shù)組s1、s2存放兩個字符串，用存放兩個字符串，用s1i表示表示s1中的第中的第i 個字符，個字符，s2j表示表示s2中的第中的第j個字符（字符編號從個字符（字符編號從1 開始），開始），用用s1i表示表示s1的前的前i個字符所構(gòu)成的子串，

44、個字符所構(gòu)成的子串，s2j表示表示s2的前的前j個字個字符構(gòu)成的子串，符構(gòu)成的子串，MaxLen(i,j)表示表示s1i 和和s2j 的最長公共子序列的最長公共子序列的長度，那么遞推關(guān)系如下：的長度，那么遞推關(guān)系如下：nif( i =0 | j = 0 ) n MaxLen(i, j) = 0 /兩個空串的最長公共子序列長度是兩個空串的最長公共子序列長度是0nelse if( s1i = 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);2、解

45、題思路 n 顯然本題目的顯然本題目的“狀態(tài)狀態(tài)”就是就是s1 中的位置中的位置i 和和s2 中的位置中的位置j。n “值值”就是就是MaxLen(i, j)。n 狀態(tài)的數(shù)目是狀態(tài)的數(shù)目是s1 長度和長度和s2 長度的乘積。可長度的乘積。可以用一個二維數(shù)組來存儲各個狀態(tài)下的以用一個二維數(shù)組來存儲各個狀態(tài)下的“值值”。n 本問題的兩個子問題，和原問題形式完全一本問題的兩個子問題，和原問題形式完全一致的，只不過規(guī)模小了一點(diǎn)。致的，只不過規(guī)模小了一點(diǎn)。3、參考程序#include #include #define MAX_LEN 1000char sz1MAX_LEN;char sz2MAX_LEN;

46、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 + ) aMaxLeni0 = 0; for( j = 0;j = nLength2; j + ) aMaxLen0j = 0;3、參考程序 for( i = 1;i = nLength1;i + ) for( j = 1; j nLen2 )

47、 aMaxLenij = nLen1; else aMaxLenij = nLen2; printf(%dn, aMaxLennLength1nLength2); return 0;陪審團(tuán)的人選 1、問題描述、問題描述 在遙遠(yuǎn)的國家佛羅布尼亞，嫌犯是否有罪，須由陪審團(tuán)決在遙遠(yuǎn)的國家佛羅布尼亞，嫌犯是否有罪，須由陪審團(tuán)決定。陪審團(tuán)是由法官從公眾中挑選的。先隨機(jī)挑選定。陪審團(tuán)是由法官從公眾中挑選的。先隨機(jī)挑選n 個人作為個人作為陪審團(tuán)的候選人，然后再從這陪審團(tuán)的候選人，然后再從這n 個人中選個人中選m 人組成陪審團(tuán)。人組成陪審團(tuán)。選選m 人的辦法是：人的辦法是： 控方和辯方會根據(jù)對候選人的喜歡程度

48、，給所有候選人打控方和辯方會根據(jù)對候選人的喜歡程度，給所有候選人打分，分值從分，分值從0 到到20。為了公平起見，法官選出陪審團(tuán)的原則。為了公平起見，法官選出陪審團(tuán)的原則是：選出的是：選出的m 個人，必須滿足辯方總分和控方總分的差的絕個人，必須滿足辯方總分和控方總分的差的絕對值最小。如果有多種選擇方案的辯方總分和控方總分的之差對值最小。如果有多種選擇方案的辯方總分和控方總分的之差的絕對值相同，那么選辯控雙方總分之和最大的方案即可。最的絕對值相同，那么選辯控雙方總分之和最大的方案即可。最終選出的方案稱為陪審團(tuán)方案。終選出的方案稱為陪審團(tuán)方案。問題描述輸入數(shù)據(jù)輸入數(shù)據(jù)輸入包含多組數(shù)據(jù)。每組數(shù)據(jù)的第

49、一行是兩個整數(shù)輸入包含多組數(shù)據(jù)。每組數(shù)據(jù)的第一行是兩個整數(shù)n 和和m，n 是候選人數(shù)目，是候選人數(shù)目，m 是陪審團(tuán)人數(shù)。注意，是陪審團(tuán)人數(shù)。注意，1=n=200, 1=m=20 而且而且 m=n。接下來的。接下來的n 行，每行表示一個候行，每行表示一個候選人的信息，它包含選人的信息，它包含2 個整數(shù)，先后是控方和辯方對該候選人個整數(shù)，先后是控方和辯方對該候選人的打分。候選人按出現(xiàn)的先后從的打分。候選人按出現(xiàn)的先后從1開始編號。兩組有效數(shù)據(jù)之開始編號。兩組有效數(shù)據(jù)之間以空行分隔。最后一組數(shù)據(jù)間以空行分隔。最后一組數(shù)據(jù)n=m=0輸出要求輸出要求對每組數(shù)據(jù)，先輸出一行，表示答案所屬的組號對每組數(shù)據(jù)，

50、先輸出一行，表示答案所屬的組號, 如如 Jury #1, Jury #2, 等。接下來的一行要象例子那樣輸出陪審團(tuán)等。接下來的一行要象例子那樣輸出陪審團(tuán)的控方總分和辯方總分。再下來一行要以升序輸出陪審團(tuán)里每的控方總分和辯方總分。再下來一行要以升序輸出陪審團(tuán)里每個成員的編號，兩個成員編號之間用空格分隔。每組輸出數(shù)據(jù)個成員的編號，兩個成員編號之間用空格分隔。每組輸出數(shù)據(jù)須以一個空行結(jié)束。須以一個空行結(jié)束。問題描述輸入樣例輸入樣例4 21 22 34 16 20 0輸出樣例輸出樣例Jury #1Best jury has value 6 for prosecution and value 4 for

51、 defence:2 32、解題思路 n為敘述方便，將任一選擇方案中，辯方總分和控方總分之差為敘述方便，將任一選擇方案中，辯方總分和控方總分之差簡稱為簡稱為“辯控差辯控差”，辯方總分和控方總分之和稱為，辯方總分和控方總分之和稱為“辯控和辯控和”。n第第i 個候選人的辯方總分和控方總分之差記為個候選人的辯方總分和控方總分之差記為V(i)，辯方總分，辯方總分和控方總分之和記為和控方總分之和記為S(i)。n現(xiàn)用現(xiàn)用f(j, k)表示，取表示，取j 個候選人，使其辯控差為個候選人，使其辯控差為k 的所有方案的所有方案中，辯控和最大的那個方案（該方案稱為中，辯控和最大的那個方案（該方案稱為“方案方案f(

52、j, k)”）的）的辯控和。辯控和。并且，我們還規(guī)定，如果沒法選并且，我們還規(guī)定，如果沒法選j 個人，使其辯控差個人，使其辯控差為為k，那么，那么f(j, k)的值就為的值就為-1，也稱方案，也稱方案f(j, k)不可行。不可行。n本題是要求選出本題是要求選出m 個人，那么，如果對個人，那么，如果對k 的所有可能的取值，的所有可能的取值，求出了所有的求出了所有的f(m, k) (-20m k 20m)，那么陪審團(tuán)，那么陪審團(tuán)方案自然就很容易找到了。方案自然就很容易找到了。2、解題思路 n問題的關(guān)鍵是建立遞推關(guān)系。顯然，方案問題的關(guān)鍵是建立遞推關(guān)系。顯然，方案f(j, k)是由某個可是由某個可行

53、的方案行的方案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(j-1, x)中，選出中，選出 f(j-1, x) + S(i) 的值最大的那個，那么方案的值最大的那個，那么方案f(j-1, x)再加上候選人再加上候選人i，就演變，就演變成了方案成了方案 f(j, k)。n由上面知一個方案都選了哪些人需要全部記

54、錄下來。不妨由上面知一個方案都選了哪些人需要全部記錄下來。不妨將將方案方案f(j, k)中最后選的那個候選人的編號，記在二維數(shù)組的元中最后選的那個候選人的編號，記在二維數(shù)組的元素素pathjk中中。那么方案。那么方案f(j, k)的倒數(shù)第二個人選的編號，的倒數(shù)第二個人選的編號，就是就是pathj-1k-Vpathjk。n假定最后算出了方案的辯控差是假定最后算出了方案的辯控差是k，那么從，那么從pathmk出發(fā)，出發(fā)，就能順藤摸瓜一步步求出所有被選中的候選人。就能順藤摸瓜一步步求出所有被選中的候選人。2、解題思路 n初始條件，只能確定初始條件，只能確定f(0, 0) = 0。由此出發(fā)，一步步自底

55、向。由此出發(fā)，一步步自底向上遞推，就能求出所有的可行方案上遞推，就能求出所有的可行方案f(m, k)( -20m k 20m)。n實際解題的時候，會用一個二維數(shù)組實際解題的時候，會用一個二維數(shù)組f 來存放來存放f(j, k)的值。而的值。而且，由于題目中辯控差的值且，由于題目中辯控差的值k 可以為負(fù)數(shù)，而程序中數(shù)租下標(biāo)可以為負(fù)數(shù)，而程序中數(shù)租下標(biāo)不能為負(fù)數(shù)，所以，在程序中不妨將辯控差的值都加上不能為負(fù)數(shù)，所以，在程序中不妨將辯控差的值都加上20m，以免下標(biāo)為負(fù)數(shù)導(dǎo)致出錯，即題目描述中，如果辯，以免下標(biāo)為負(fù)數(shù)導(dǎo)致出錯，即題目描述中，如果辯控差為控差為0，則在程序中辯控差為，則在程序中辯控差為20

56、m。3、參考程序#include #include #include int f301000;int Path301000;int P300; /控方打分控方打分int D300; /辯方打分辯方打分int Answer30; /存放最終方案的人選存放最終方案的人選int CompareInt(const void * e1, const void * e2) return * (int *) e1) - * (int *) e2);3、參考程序int main(void) int i, j, k; int t1, t2; int n, m; int nMinP_D; /辯控雙方總分一樣時的辯

57、控差辯控雙方總分一樣時的辯控差 int nCaseNo;/測試數(shù)據(jù)編號測試數(shù)據(jù)編號 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(f); memset(Path, 0, sizeof(Path); nMinP_D=m*20; /題目中的辯控差為題目中的辯控差為0 /對應(yīng)到程序中辯控差就是對應(yīng)到程序中辯控差就是m*20 f0nMinP_D=0; /選選0 個人辯控差為個人辯控差為0 的方案，其辯控和就是的方案，其辯控和

58、就是03、參考程序 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; while(t10&Patht1t2!=i) /t2減去編號為減去編號為Patht1t2的辯控差的辯控差 t2-=PPatht1t2-DPatht1t2; t1-;/減少減少1人人 if(t1=0) /沒有發(fā)現(xiàn)沒有發(fā)現(xiàn) fj+1k+Pi-Di=fjk+Pi+Di; Pathj+1k+Pi-D

59、i=i; 3、參考程序 i=nMinP_D; j=0; while(fmi+j0&fmi-jfmi-j)/絕對值相同時找辯控和最大的絕對值相同時找辯控和最大的 k=i+j; else k=i-j; printf(Jury #%dn, nCaseNo); printf(Best jury 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;/減去

60、辯控差減去辯控差 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;購物問題 1、問題描述、問題描述 由于換季，由于換季，ACM商場推出優(yōu)惠活動，以超低價格出售商場推出優(yōu)惠活動，以超低價格出售若干種商品。但是，商場為避免過分虧本，規(guī)定某些若干種商品。但是，商場為避免過分虧本，規(guī)定某些商品不能同時購買，而且每種超低價商品只能買一件。商品不能同時購買，而且每種超低價商品只能買一件。