1、第十四講第十四講ACMACM算法與程序設計算法與程序設計2/28Help Jimmy 1、問題描述、問題描述 Help Jimmy 是在下圖所示的場景上完成的游戲：是在下圖所示的場景上完成的游戲：3/28問題描述問題描述 場景中包括多個長度和高度各不相同的平臺。地面是最低場景中包括多個長度和高度各不相同的平臺。地面是最低的平臺，高度為零，長度無限。的平臺，高度為零，長度無限。 Jimmy 老鼠在時刻老鼠在時刻0 從高于所有平臺的某處開始下落，它從高于所有平臺的某處開始下落，它的下落速度始終為的下落速度始終為1 米米/秒。當秒。當Jimmy 落到某個平臺上時，游落到某個平臺上時，游戲者選擇讓它向

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

3、空格分隔。，用空格分隔。N 是是平臺的數目（不包括地面），平臺的數目（不包括地面），X 和和Y 是是Jimmy 開始下落的位開始下落的位置的橫豎坐標，置的橫豎坐標，MAX 是一次下落的最大高度。接下來的是一次下落的最大高度。接下來的N 行行每行描述一個平臺，包括三個整數，每行描述一個平臺，包括三個整數，X1i，X2i和和Hi。Hi表示平臺的高度，表示平臺的高度，X1i和和X2i表示平臺左右端點的橫坐表示平臺左右端點的橫坐標。標。1= N = 1000，-20000 = X, X1i, X2i = 20000，0 Hi Y = 20000（i = 1.N）。所有坐標）。所有坐標的單位都是米。的單

4、位都是米。n Jimmy 的大小和平臺的厚度均忽略不計。如果的大小和平臺的厚度均忽略不計。如果Jimmy 恰好恰好落在某個平臺的邊緣，被視為落在平臺上。所有的平臺均不重落在某個平臺的邊緣，被視為落在平臺上。所有的平臺均不重疊或相連。測試數據保疊或相連。測試數據保Jimmy 一定能安全到達地面。一定能安全到達地面。5/28問題描述問題描述輸出要求輸出要求對輸入的每組測試數據，輸出一個整數，對輸入的每組測試數據，輸出一個整數，Jimmy 到地面時可到地面時可能的最早時間。能的最早時間。輸入樣例輸入樣例13 8 17 200 10 80 10 134 14 3輸出樣例輸出樣例236/282、解題思路

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

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

7、態”對對應的應的“值值”有兩部分，是兩個子問題的解，即從該板子左端出有兩部分，是兩個子問題的解，即從該板子左端出發到達地面的最短時間，和從該板子右端出發到達地面的最短發到達地面的最短時間，和從該板子右端出發到達地面的最短時間。時間。n 不妨認為不妨認為Jimmy 開始的位置是一個編號為開始的位置是一個編號為0，長度為，長度為0 的板的板子，假設子，假設LeftMinTime(k)表示從表示從k 號板子左端到地面的最短號板子左端到地面的最短時間，時間，RightMinTime(k)表示從表示從k 號板子右端到地面的最短號板子右端到地面的最短時間，那么，求板子時間，那么，求板子k 左端點到地面的最

8、短時間的方法如下：左端點到地面的最短時間的方法如下：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(LeftMinTime(m)+Lx(k)-Lx(m), RightMinTime(m)+Rx(m)-Lx(k); 8/282、解題思路解題思路 n 上面，上面，h(i)就代表就

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

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

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

12、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; 11/283、參考程序參考程序 else /沒找到沒找到 if( y max )/離地面太高離地面太高 return INFINITE; else return y; /特殊情況處理完畢特殊情況處理完畢 int nLeftTime = y - aPlatformi.h + x - a

13、Platformi.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 += aRightMinTimei; if( nLeftTime nRightTime ) return nLeft

14、Time; return nRightTime;12/283、參考程序參考程序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的板子的板子 aP

15、latform0.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;思考題：重新編寫此程序，要求不使用遞思考題：重新編寫此程序，要求不使用遞歸函數歸函數13/28最長公共子序列最長公共子序列 1、問題描述、問題描述 我們稱序列我們稱序列Z =

16、 是序列是序列X = 的子序列當且僅當存在嚴格上升的序列的子序列當且僅當存在嚴格上升的序列，使得對使得對j = 1, 2, . ,k, 有有xij = zj。比如。比如Z = 是是X = 的子序列。的子序列。現在給出兩個序列現在給出兩個序列X 和和Y，你的任務是找到，你的任務是找到X 和和Y 的最大公共的最大公共子序列，也就是說要找到一個最長的序列子序列，也就是說要找到一個最長的序列Z，使得，使得Z 既是既是X 的的子序列也是子序列也是Y 的子序列。的子序列。輸入數據輸入數據輸入包括多組測試數據。每組數據包括一行，給出兩個長度不輸入包括多組測試數據。每組數據包括一行，給出兩個長度不超過超過20

17、0 的字符串，表示兩個序列。兩個字符串之間由若干的字符串，表示兩個序列。兩個字符串之間由若干個空格隔開。個空格隔開。14/28問題描述問題描述 輸出要求輸出要求 對每組輸入數據，輸出一行，給出兩個序列的最大公共子序對每組輸入數據，輸出一行，給出兩個序列的最大公共子序列的長度。列的長度。 輸入樣例輸入樣例 abcfbc abfcab programming contest abcd mnp 輸出樣例輸出樣例 4 2 015/282、解題思路解題思路 n用字符數組用字符數組s1、s2存放兩個字符串，用存放兩個字符串，用s1i表示表示s1中的第中的第i 個字符，個字符，s2j表示表示s2中的第中的第

18、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( s1i = s2j )n MaxLen(i, j) = MaxLen(i-1, j-1 ) + 1;nelse

19、 n MaxLen(i,j) = Max(MaxLen(i, j-1), MaxLen(i-1, j);16/282、解題思路解題思路 n 顯然本題目的顯然本題目的“狀態狀態”就是就是s1 中的位置中的位置i 和和s2 中的位置中的位置j。n “值值”就是就是MaxLen(i, j)。n 狀態的數目是狀態的數目是s1 長度和長度和s2 長度的乘積。可長度的乘積。可以用一個二維數組來存儲各個狀態下的以用一個二維數組來存儲各個狀態下的“值值”。n 本問題的兩個子問題，和原問題形式完全一本問題的兩個子問題，和原問題形式完全一致的，只不過規模小了一點。致的，只不過規模小了一點。17/283、參考程序參

20、考程序#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 + ) aMaxLeni0 = 0; for( j = 0;j = nLength2; j + )

21、 aMaxLen0j = 0;18/283、參考程序 for( i = 1;i = nLength1;i + ) for( j = 1; j nLen2 ) aMaxLenij = nLen1; else aMaxLenij = nLen2; printf(%dn, aMaxLennLength1nLength2); return 0;19/28陪審團的人選陪審團的人選 1、問題描述、問題描述 在遙遠的國家佛羅布尼亞，嫌犯是否有罪，須由陪審團決在遙遠的國家佛羅布尼亞，嫌犯是否有罪，須由陪審團決定。陪審團是由法官從公眾中挑選的。先隨機挑選定。陪審團是由法官從公眾中挑選的。先隨機挑選n 個人作為個

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

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

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

25、21/28問題描述問題描述輸入樣例輸入樣例4 21 22 34 16 20 0輸出樣例輸出樣例Jury #1Best jury has value 6 for prosecution and value 4 for defence:2 322/282、解題思路解題思路 n為敘述方便，將任一選擇方案中，辯方總分和控方總分之差為敘述方便，將任一選擇方案中，辯方總分和控方總分之差簡稱為簡稱為“辯控差辯控差”，辯方總分和控方總分之和稱為，辯方總分和控方總分之和稱為“辯控和辯控和”。n第第i 個候選人的辯方總分和控方總分之差記為個候選人的辯方總分和控方總分之差記為V(i)，辯方總分，辯方總分和控方總分之

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

27、m, k) (-20m k 20m)，那么陪審團，那么陪審團方案自然就很容易找到了。方案自然就很容易找到了。23/282、解題思路解題思路 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

28、(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假定最后算出了方案的辯控差是

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

30、而程序中數租下標不能為負數，所以，在程序中不妨將辯控差的值都加上不能為負數，所以，在程序中不妨將辯控差的值都加上20m，以免下標為負數導致出錯，即題目描述中，如果辯，以免下標為負數導致出錯，即題目描述中，如果辯控差為控差為0，則在程序中辯控差為，則在程序中辯控差為20m。25/283、參考程序參考程序#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);26/283、參考程序參考程序int main(void) int i, j, k; int t1, t2; int n, m; int nMinP_D; /辯控雙方總分一樣時的辯控差辯控雙方總分一樣時的辯控差 int nCaseNo;/測試數據編號測試數據編號 nCaseNo=0; scanf(%d%d