acm递归与动态规划(三)

《acm递归与动态规划(三)》由会员分享，可在线阅读，更多相关《acm递归与动态规划(三)（28页珍藏版）》请在金锄头文库上搜索。

1、第十四讲,递归与动态规划(三),ACM算法与程序设计,2/28,Help Jimmy,1、问题描述,“Help Jimmy“ 是在下图所示的场景上完成的游戏：,3/28,问题描述,场景中包括多个长度和高度各不相同的平台。地面是最低的平台，高度为零，长度无限。 Jimmy 老鼠在时刻0 从高于所有平台的某处开始下落，它的下落速度始终为1 米/秒。当Jimmy 落到某个平台上时，游戏者选择让它向左还是向右跑，它跑动的速度也是1 米/秒。当Jimmy 跑到平台的边缘时，开始继续下落。Jimmy 每次下落的高度不能超过MAX 米，不然就会摔死，游戏也会结束。 设计一个程序，计算Jimmy 到地面时可能

2、的最早时间。,4/28,问题描述,输入数据 第一行是测试数据的组数t（0 = t = 20）。每组测试数据的第一行是四个整数N，X，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 = 1N）。所有坐标的单位都是米。 Jimmy 的大小和平台的厚度均忽略不计。如果Jim

3、my 恰好落在某个平台的边缘，被视为落在平台上。所有的平台均不重叠或相连。测试数据保Jimmy 一定能安全到达地面。,5/28,问题描述,输出要求 对输入的每组测试数据，输出一个整数，Jimmy 到地面时可能的最早时间。 输入样例 1 3 8 17 20 0 10 8 0 10 13 4 14 3 输出样例 23,6/28,2、解题思路,此题目的“子问题”是什么呢？ Jimmy 跳到一块板上后，可以有两种选择，向左走或向右走。走到左端和走到右端所需的时间，容易算出。 如果我们能知道，以左端为起点到达地面的最短时间，和以右端为起点到达地面的最短时间，那么向左走还是向右走，就很容选择了。 因此，整

4、个问题就被分解成两个子问题，即Jimmy 所在位置下方第一块板左端为起点到地面的最短时间，和右端为起点到地面的最短时间。这两个子问题在形式上和原问题是完全一致的。 将板子从上到下从1 开始进行无重复的编号(高度相同的板子，哪块编号在前无所谓)，那么，和上面两个子问题相关的变量就只有板子的编号。,7/28,2、解题思路,所以，本题目的“状态”就是板子编号，而一个“状态”对应的“值”有两部分，是两个子问题的解，即从该板子左端出发到达地面的最短时间，和从该板子右端出发到达地面的最短时间。 不妨认为Jimmy 开始的位置是一个编号为0，长度为0 的板子，假设LeftMinTime(k)表示从k 号板子

5、左端到地面的最短时间，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(LeftMinTime(m)+Lx(k)-Lx(m), RightMinTime(m)+Rx(m)-Lx(k);,8/28,2、解题思路,上面，h(i

6、)就代表i 号板子的高度，Lx(i)就代表i 号板子左端点的横坐标，Rx(i)就代表i号板子右端点的横坐标。那么 h(k)-h(m) 当然就是从k 号板子跳到m 号板子所需要的时间，Lx(k)-Lx(m) 就是从m 号板子的落脚点走到m 号板子左端点的时间，Rx(m)-Lx(k)就是从m号板子的落脚点走到右端点所需的时间。 求RightMinTime(k)的过程类似。 不妨认为Jimmy 开始的位置是一个编号为0，长度为0 的板子，那么整个问题就是要求LeftMinTime(0)。 输入数据中，板子并没有按高度排序，所以程序中一定要首先将板子排序。,9/28,3、参考程序,#include #

7、include #include #define MAX_N 1000 #define INFINITE 1000000 int 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 =

8、 (Platform * ) e2; return p2-h - p1-h; /从大到小排列 ,10/28,3、参考程序,int MinTime( 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 = x) break; if( i max )/太高 return INFINITE; ,11/28,3、参考程序,else /没找到 if( y max )/离地面太高 return INFINITE;

9、 else return y; /特殊情况处理完毕 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; nRightTim

10、e += aRightMinTimei; if( nLeftTime nRightTime ) return nLeftTime; return nRightTime; ,12/28,3、参考程序,int main(void) scanf(“%d“, ,思考题：重新编写此程序，要求不使用递归函数,13/28,最长公共子序列,1、问题描述,我们称序列Z = 是序列X = 的子序列当且仅当存在严格上升的序列，使得对j = 1, 2, . ,k, 有xij = zj。比如Z = 是X = 的子序列。 现在给出两个序列X 和Y，你的任务是找到X 和Y 的最大公共子序列，也就是说要找到一个最长的序列Z，

11、使得Z 既是X 的子序列也是Y 的子序列。 输入数据 输入包括多组测试数据。每组数据包括一行，给出两个长度不超过200 的字符串，表示两个序列。两个字符串之间由若干个空格隔开。,14/28,问题描述,输出要求 对每组输入数据，输出一行，给出两个序列的最大公共子序列的长度。 输入样例 abcfbc abfcab programming contest abcd mnp 输出样例 4 2 0,15/28,2、解题思路,用字符数组s1、s2存放两个字符串，用s1i表示s1中的第i 个字符，s2j表示s2中的第j个字符（字符编号从1 开始），用s1i表示s1的前i个字符所构成的子串，s2j表示s2的前

12、j个字符构成的子串，MaxLen(i,j)表示s1i 和s2j 的最长公共子序列的长度，那么递推关系如下： if( i =0 | j = 0 ) MaxLen(i, j) = 0 /两个空串的最长公共子序列长度是0 else if( s1i = s2j ) MaxLen(i, j) = MaxLen(i-1, j-1 ) + 1; else MaxLen(i,j) = Max(MaxLen(i, j-1), MaxLen(i-1, j);,16/28,2、解题思路,显然本题目的“状态”就是s1 中的位置i 和s2 中的位置j。 “值”就是MaxLen(i, j)。 状态的数目是s1 长度和s2

13、 长度的乘积。可以用一个二维数组来存储各个状态下的“值”。 本问题的两个子问题，和原问题形式完全一致的，只不过规模小了一点。,17/28,3、参考程序,#include #include #define MAX_LEN 1000 char 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,

14、j; for( i = 0;i = nLength1; i + ) aMaxLeni0 = 0; for( j = 0;j = nLength2; j + ) aMaxLen0j = 0;,18/28,3、参考程序,for( i = 1;i nLen2 ) aMaxLenij = nLen1; else aMaxLenij = nLen2; printf(“%dn“, aMaxLennLength1nLength2); return 0; ,19/28,陪审团的人选,1、问题描述,在遥远的国家佛罗布尼亚，嫌犯是否有罪，须由陪审团决定。陪审团是由法官从公众中挑选的。先随机挑选n 个人作为陪审团的

15、候选人，然后再从这n 个人中选m 人组成陪审团。选m 人的办法是： 控方和辩方会根据对候选人的喜欢程度，给所有候选人打分，分值从0 到20。为了公平起见，法官选出陪审团的原则是：选出的m 个人，必须满足辩方总分和控方总分的差的绝对值最小。如果有多种选择方案的辩方总分和控方总分的之差的绝对值相同，那么选辩控双方总分之和最大的方案即可。最终选出的方案称为陪审团方案。,20/28,问题描述,输入数据 输入包含多组数据。每组数据的第一行是两个整数n 和m，n 是候选人数目，m 是陪审团人数。注意，1=n=200, 1=m=20 而且 m=n。接下来的n 行，每行表示一个候选人的信息，它包含2 个整数，

16、先后是控方和辩方对该候选人的打分。候选人按出现的先后从1开始编号。两组有效数据之间以空行分隔。最后一组数据n=m=0 输出要求 对每组数据，先输出一行，表示答案所属的组号, 如 Jury #1, Jury #2, 等。接下来的一行要象例子那样输出陪审团的控方总分和辩方总分。再下来一行要以升序输出陪审团里每个成员的编号，两个成员编号之间用空格分隔。每组输出数据须以一个空行结束。,21/28,问题描述,输入样例 4 2 1 2 2 3 4 1 6 2 0 0 输出样例 Jury #1 Best jury has value 6 for prosecution and value 4 for def

17、ence: 2 3,22/28,2、解题思路,为叙述方便，将任一选择方案中，辩方总分和控方总分之差简称为“辩控差”，辩方总分和控方总分之和称为“辩控和”。 第i 个候选人的辩方总分和控方总分之差记为V(i)，辩方总分和控方总分之和记为S(i)。 现用f(j, k)表示，取j 个候选人，使其辩控差为k 的所有方案中，辩控和最大的那个方案（该方案称为“方案f(j, k)”）的辩控和。并且，我们还规定，如果没法选j 个人，使其辩控差为k，那么f(j, k)的值就为-1，也称方案f(j, k)不可行。 本题是要求选出m 个人，那么，如果对k 的所有可能的取值，求出了所有的f(m, k) (-20m k 20m)，那么陪审团方案自然就很容易找到了。,