《第十四周递归与动态规划三》由会员分享，可在线阅读，更多相关《第十四周递归与动态规划三（28页珍藏版）》请在金锄头文库上搜索。
1、第十四讲第十四讲递归与动态规划递归与动态规划(三三)ACMACM算法与程序设计算法与程序设计Help Jimmy 1、问题描述、问题描述 Help Jimmy 是在下图所示的场景上完成的游戏：是在下图所示的场景上完成的游戏：2问题描述问题描述 场景中包括多个长度和高度各不相同的平台。地面是最低的场景中包括多个长度和高度各不相同的平台。地面是最低的平台，高度为零，长度无限。平台，高度为零，长度无限。 Jimmy 老鼠在时刻老鼠在时刻0 从高于所有平台的某处开始下落，它从高于所有平台的某处开始下落，它的下落速度始终为的下落速度始终为1 米米/秒。当秒。当Jimmy 落到某个平台上时，游落到某个平台
2、上时，游戏者选择让它向左还是向右跑，它跑动的速度也是戏者选择让它向左还是向右跑，它跑动的速度也是1 米米/秒。秒。当当Jimmy 跑到平台的边缘时，开始继续下落。跑到平台的边缘时，开始继续下落。Jimmy 每次下每次下落的高度不能超过落的高度不能超过MAX 米，不然就会摔死，游戏也会结束。米，不然就会摔死，游戏也会结束。 设计一个程序，计算设计一个程序，计算Jimmy 到地面时可能的最早时间。到地面时可能的最早时间。3问题描述问题描述输入数据输入数据n 第一行是测试数据的组数第一行是测试数据的组数t（0 = t = 20）。每组测试数）。每组测试数据的第一行是四个整数据的第一行是四个整数N，X
3、，Y，MAX，用空格分隔。，用空格分隔。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 一定能安全到达地面。一定能安全到达地面。4问题描述问题描述输出要求输出要求对输入的每组测试数据，输出一个整数，对输入的每组测试数据，输出一个整数，Jimmy 到地面时可到地面时可能的最早时间。能的最早时间。输入样例输入样例13 8 17 200 10 80 10 134 14 3输出样例输出样例2352、解题
5、思路解题思路 n 此题目的此题目的“子问题子问题”是什么呢？是什么呢？n Jimmy 跳到一块板上后，可以有两种选择，向左走或向右跳到一块板上后，可以有两种选择，向左走或向右走。走到左端和走到右端所需的时间，容易算出。走。走到左端和走到右端所需的时间，容易算出。n 如果我们能知道，以左端为起点到达地面的最短时间，和以如果我们能知道，以左端为起点到达地面的最短时间，和以右端为起点到达地面的最短时间，那么向左走还是向右走，就右端为起点到达地面的最短时间，那么向左走还是向右走，就很容选择了。很容选择了。n 因此，整个问题就被分解成两个子问题，即因此，整个问题就被分解成两个子问题，即Jimmy 所在位
6、所在位置下方第一块板左端为起点到地面的最短时间，和右端为起点置下方第一块板左端为起点到地面的最短时间，和右端为起点到地面的最短时间。这两个子问题在形式上和原问题是完全一到地面的最短时间。这两个子问题在形式上和原问题是完全一致的。致的。n 将板子从上到下从将板子从上到下从1 开始进行无重复的编号开始进行无重复的编号(高度相同的板高度相同的板子，哪块编号在前无所谓子，哪块编号在前无所谓)，那么，和上面两个子问题相关的，那么，和上面两个子问题相关的变量就只有板子的编号。变量就只有板子的编号。62、解题思路 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); 72、解题思路解题思路 n 上面，上面，h(i)就代表就代表i
9、号板子的高度，号板子的高度，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 不妨认为不妨认为Jim
10、my 开始的位置是一个编号为开始的位置是一个编号为0，长度为，长度为0 的板的板子，那么整个问题就是要求子，那么整个问题就是要求LeftMinTime(0)。n 输入数据中，板子并没有按高度排序，所以程序中一定要首输入数据中，板子并没有按高度排序，所以程序中一定要首先将板子排序。先将板子排序。83、参考程序#include #include #include #define MAX_N 1000#define INFINITE 1000000int t, n, x, y, max;struct Platform int Lx, Rx, h; ;Platform aPlatformMAX_N +
11、 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; /从大到小排列从大到小排列93、参考程序参考程序int MinTime( int L, bool bLeft ) int y = aPlatformL.h; int i, x; if( bLeft ) x =
12、 aPlatformL.Lx; else x = aPlatformL.Rx; for( i = L + 1;i = n;i + ) /找到下一张板子找到下一张板子 if( aPlatformi.Lx = x) break; if( i max )/太高太高 return INFINITE; 103、参考程序参考程序 else /没找到没找到 if( y max )/离地面太高离地面太高 return INFINITE; else return y; /特殊情况处理完毕特殊情况处理完毕 int nLeftTime = y - aPlatformi.h + x - aPlatformi.Lx;
13、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 nLeftTime; return n
14、RightTime;113、参考程序参考程序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
15、; 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;思考题：重新编写此程序，要求不使用递归思考题：重新编写此程序，要求不使用递归函数函数12最长公共子序列最长公共子序列 1、问题描述、问题描述 我我们们称称序序列列Z = 是是序序列列X = 的的子子序序列列当当且且仅仅当当存存在在严严格格上上升升的的序序列列，使使得得对对
16、j = 1, 2, . ,k, 有有xij = zj。比比如如Z = 是是X = 的子序列。的子序列。现现在在给给出出两两个个序序列列X 和和Y，你你的的任任务务是是找找到到X 和和Y 的的最最大大公公共共子子序序列列，也也就就是是说说要要找找到到一一个个最最长长的的序序列列Z，使使得得Z 既既是是X 的的子序列也是子序列也是Y 的子序列。的子序列。输入数据输入数据输输入入包包括括多多组组测测试试数数据据。每每组组数数据据包包括括一一行行，给给出出两两个个长长度度不不超超过过200 的的字字符符串串，表表示示两两个个序序列列。两两个个字字符符串串之之间间由由若若干干个个空格隔开。空格隔开。13
17、问题描述问题描述 输出要求输出要求 对每组输入数据，输出一行，给出两个序列的最大公共子序对每组输入数据，输出一行，给出两个序列的最大公共子序列的长度。列的长度。 输入样例输入样例 abcfbc abfcab programming contest abcd mnp 输出样例输出样例 4 2 0142、解题思路解题思路 n用用字字符符数数组组s1、s2存存放放两两个个字字符符串串，用用s1i表表示示s1中中的的第第i 个个字字符符，s2j表表示示s2中中的的第第j个个字字符符（字字符符编编号号从从1 开开始始），用用s1i表表示示s1的的前前i个个字字符符所所构构成成的的子子串串，s2j表表示示
18、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 n MaxLen(i,j) = Max(MaxLen(i, j-1), MaxLen(i-1, j);152、解题思路解题思路 n 显显然然本本
19、题题目目的的“状状态态”就就是是s1 中中的的位位置置i 和和s2 中的位置中的位置j。n “值值”就是就是MaxLen(i, j)。n 状状态态的的数数目目是是s1 长长度度和和s2 长长度度的的乘乘积积。可可以用一个二维数组来存储各个状态下的以用一个二维数组来存储各个状态下的“值值”。n 本本问问题题的的两两个个子子问问题题，和和原原问问题题形形式式完完全全一一致的，只不过规模小了一点。致的，只不过规模小了一点。163、参考程序参考程序#include #include #define MAX_LEN 1000char sz1MAX_LEN;char sz2MAX_LEN;int aMax
20、LenMAX_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;173、参考程序 for( i = 1;i = nLength1;i + ) for( j = 1; j nLen2 ) aMaxL
21、enij = nLen1; else aMaxLenij = nLen2; printf(%dn, aMaxLennLength1nLength2); return 0;18陪审团的人选陪审团的人选 1、问题描述、问题描述 在在遥遥远远的的国国家家佛佛罗罗布布尼尼亚亚，嫌嫌犯犯是是否否有有罪罪，须须由由陪陪审审团团决决定定。陪陪审审团团是是由由法法官官从从公公众众中中挑挑选选的的。先先随随机机挑挑选选n 个个人人作作为为陪陪审审团团的的候候选选人人，然然后后再再从从这这n 个个人人中中选选m 人人组组成成陪陪审审团团。选选m 人的办法是：人的办法是： 控控方方和和辩辩方方会会根根据据对对候候选
22、选人人的的喜喜欢欢程程度度，给给所所有有候候选选人人打打分分，分分值值从从0 到到20。为为了了公公平平起起见见，法法官官选选出出陪陪审审团团的的原原则则是是：选选出出的的m 个个人人，必必须须满满足足辩辩方方总总分分和和控控方方总总分分的的差差的的绝绝对对值值最最小小。如如果果有有多多种种选选择择方方案案的的辩辩方方总总分分和和控控方方总总分分的的之之差差的的绝绝对对值值相相同同，那那么么选选辩辩控控双双方方总总分分之之和和最最大大的的方方案案即即可可。最最终终选选出出的的方方案称为陪审团方案。案称为陪审团方案。19问题描述问题描述输入数据输入数据输入包含多组数据。每组数据的第一行是两个整数
23、输入包含多组数据。每组数据的第一行是两个整数n 和和m，n 是候选人数目，是候选人数目，m 是陪审团人数。注意，是陪审团人数。注意，1=n=200, 1=m=20 而且而且 m=n。接下来的。接下来的n 行，每行表示一个候行，每行表示一个候选人的信息，它包含选人的信息，它包含2 个整数，先后是控方和辩方对该候选人个整数，先后是控方和辩方对该候选人的打分。候选人按出现的先后从的打分。候选人按出现的先后从1开始编号。两组有效数据之开始编号。两组有效数据之间以空行分隔。最后一组数据间以空行分隔。最后一组数据n=m=0输出要求输出要求对每组数据，先输出一行，表示答案所属的组号对每组数据，先输出一行，表
24、示答案所属的组号, 如如 Jury #1, Jury #2, 等。接下来的一行要象例子那样输出陪审团等。接下来的一行要象例子那样输出陪审团的控方总分和辩方总分。再下来一行要以升序输出陪审团里每的控方总分和辩方总分。再下来一行要以升序输出陪审团里每个成员的编号，两个成员编号之间用空格分隔。每组输出数据个成员的编号，两个成员编号之间用空格分隔。每组输出数据须以一个空行结束。须以一个空行结束。20问题描述问题描述输入样例输入样例4 21 22 34 16 20 0输出样例输出样例Jury #1Best jury has value 6 for prosecution and value 4 for
25、defence:2 3212、解题思路解题思路 n为为叙叙述述方方便便，将将任任一一选选择择方方案案中中，辩辩方方总总分分和和控控方方总总分分之之差差简称为简称为“辩控差辩控差”，辩方总分和控方总分之和称为，辩方总分和控方总分之和称为“辩控和辩控和”。n第第i 个个候候选选人人的的辩辩方方总总分分和和控控方方总总分分之之差差记记为为V(i)，辩辩方方总总分分和控方总分之和记为和控方总分之和记为S(i)。n现现用用f(j, k)表表示示，取取j 个个候候选选人人，使使其其辩辩控控差差为为k 的的所所有有方方案案中中，辩辩控控和和最最大大的的那那个个方方案案（该该方方案案称称为为“方方案案f(j,
26、 k)”）的的辩辩控控和和。并并且且，我我们们还还规规定定，如如果果没没法法选选j 个个人人，使使其其辩辩控控差差为为k，那么，那么f(j, k)的值就为的值就为-1，也称方案，也称方案f(j, k)不可行。不可行。n本本题题是是要要求求选选出出m 个个人人，那那么么，如如果果对对k 的的所所有有可可能能的的取取值值，求求出出了了所所有有的的f(m, k) (-20m k 20m)，那那么么陪陪审审团团方方案自然就很容易找到了。案自然就很容易找到了。222、解题思路解题思路 n问问题题的的关关键键是是建建立立递递推推关关系系。显显然然，方方案案f(j, k)是是由由某某个个可可行的方案行的方案
27、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由由上上面面知知一一个个方方案案都都选选了了哪哪些些人人需需要
28、要全全部部记记录录下下来来。不不妨妨将将方方案案f(j, k)中中最最后后选选的的那那个个候候选选人人的的编编号号，记记在在二二维维数数组组的的元元素素pathjk中中。那那么么方方案案f(j, k)的的倒倒数数第第二二个个人人选选的的编编号号，就是就是pathj-1k-Vpathjk。n假假定定最最后后算算出出了了方方案案的的辩辩控控差差是是k，那那么么从从pathmk出出发发，就能顺藤摸瓜一步步求出所有被选中的候选人。就能顺藤摸瓜一步步求出所有被选中的候选人。232、解题思路解题思路 n初初始始条条件件，只只能能确确定定f(0, 0) = 0。由由此此出出发发，一一步步步步自自底底向向上上
29、递递推推，就就能能求求出出所所有有的的可可行行方方案案f(m, k)( -20m k 20m)。n实实际际解解题题的的时时候候，会会用用一一个个二二维维数数组组f 来来存存放放f(j, k)的的值值。而而且且，由由于于题题目目中中辩辩控控差差的的值值k 可可以以为为负负数数，而而程程序序中中数数租租下下标标不不能能为为负负数数，所所以以，在在程程序序中中不不妨妨将将辩辩控控差差的的值值都都加加上上20m，以以免免下下标标为为负负数数导导致致出出错错，即即题题目目描描述述中中，如如果果辩辩控控差差为为0，则在程序中辩控差为，则在程序中辩控差为20m。243、参考程序参考程序#include #i
30、nclude #include int f301000;int Path301000;int P300; /控方打分控方打分int D300; /辩方打分辩方打分int Answer30; /存放最终方案的人选存放最终方案的人选int CompareInt(const void * e1, const void * e2) return * (int *) e1) - * (int *) e2);253、参考程序参考程序int main(void) int i, j, k; int t1, t2; int n, m; int nMinP_D; /辩控双方总分一样时的辩控差辩控双方总分一样时的辩
31、控差 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(f); memset(Path, 0, sizeof(Path); nMinP_D=m*20; /题目中的辩控差为题目中的辩控差为0 /对应到程序中辩控差就是对应到程序中辩控差就是m*20 f0nMinP_D=0; /选选0 个人辩控差为个人辩控差为0 的方案，其辩控和就是的方案，其辩控和就是0263、参考程序 f
32、or(j=0;jm;j+) /每次循环选出第每次循环选出第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) /没有发现没有发现 fj+1k+Pi-Di=fjk+Pi+Di; Pathj+1k+Pi-Di=i; 273、参考
33、程序 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;/减去辩控差减去辩控差 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;28
