第十四周 递归与动态规划(三)

第十四讲递归与动态规划(三)ACM算法与程序设计2/28HelpJimmy1、问题描述HelpJimmy是在下图所示的场景上完成的游戏：3/28问题描述场景中包括多个长度和高度各不相同的平台。地面是最低的平台，高度为零，长度无限。Jimmy老鼠在时刻0从高于所有平台的某处开始下落，它的下落速度始终为1米/秒。当Jimmy落到某个平台上时，游戏者选择让它向左还是向右跑，它跑动的速度也是1米/秒。当Jimmy跑到平台的边缘时，开始继续下落。Jimmy每次下落的高度不能超过MAX米，不然就会摔死，游戏也会结束。设计一个程序，计算Jimmy到地面时可能的最早时间。4/28问题描述输入数据第一行是测试数据的组数t（0=t=20）。每组测试数据的第一行是四个整数N，X，Y，MAX，用空格分隔。N是平台的数目（不包括地面），X和Y是Jimmy开始下落的位置的横竖坐标，MAX是一次下落的最大高度。接下来的N行每行描述一个平台，包括三个整数，X1[i]，X2[i]和H[i]。H[i]表示平台的高度，X1[i]和X2[i]表示平台左右端点的横坐标。1=N=1000，-20000=X,X1[i],X2[i]=20000，0H[i]Y=20000（i=1..N）。所有坐标的单位都是米。Jimmy的大小和平台的厚度均忽略不计。如果Jimmy恰好落在某个平台的边缘，被视为落在平台上。所有的平台均不重叠或相连。测试数据保Jimmy一定能安全到达地面。5/28问题描述输出要求对输入的每组测试数据，输出一个整数，Jimmy到地面时可能的最早时间。输入样例13817200108010134143输出样例236/282、解题思路此题目的“子问题”是什么呢？Jimmy跳到一块板上后，可以有两种选择，向左走或向右走。走到左端和走到右端所需的时间，容易算出。如果我们能知道，以左端为起点到达地面的最短时间，和以右端为起点到达地面的最短时间，那么向左走还是向右走，就很容选择了。因此，整个问题就被分解成两个子问题，即Jimmy所在位置下方第一块板左端为起点到地面的最短时间，和右端为起点到地面的最短时间。这两个子问题在形式上和原问题是完全一致的。将板子从上到下从1开始进行无重复的编号(高度相同的板子，哪块编号在前无所谓)，那么，和上面两个子问题相关的变量就只有板子的编号。7/282、解题思路所以，本题目的“状态”就是板子编号，而一个“状态”对应的“值”有两部分，是两个子问题的解，即从该板子左端出发到达地面的最短时间，和从该板子右端出发到达地面的最短时间。不妨认为Jimmy开始的位置是一个编号为0，长度为0的板子，假设LeftMinTime(k)表示从k号板子左端到地面的最短时间，RightMinTime(k)表示从k号板子右端到地面的最短时间，那么，求板子k左端点到地面的最短时间的方法如下：if(板子k左端正下方没有别的板子){if(板子k的高度h(k)大于Max)LeftMinTime(k)=∞;elseLeftMinTime(k)=h(k);}elseif(板子k左端正下方的板子编号是m)LeftMinTime(k)=h(k)-h(m)+Min(LeftMinTime(m)+Lx(k)-Lx(m),RightMinTime(m)+Rx(m)-Lx(k));8/282、解题思路上面，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号板子的落脚点走到右端点所需的时间。求RightMinTime(k)的过程类似。不妨认为Jimmy开始的位置是一个编号为0，长度为0的板子，那么整个问题就是要求LeftMinTime(0)。输入数据中，板子并没有按高度排序，所以程序中一定要首先将板子排序。9/283、参考程序#includestdio.h#includememory.h#includestdlib.h#defineMAX_N1000#defineINFINITE1000000intt,n,x,y,max;structPlatform{intLx,Rx,h;};PlatformaPlatform[MAX_N+10];intaLeftMinTime[MAX_N+10];intaRightMinTime[MAX_N+10];intMyCompare(constvoid*e1,constvoid*e2){Platform*p1,*p2;p1=(Platform*)e1;p2=(Platform*)e2;returnp2-h-p1-h;//从大到小排列}10/283、参考程序intMinTime(intL,boolbLeft){inty=aPlatform[L].h;inti,x;if(bLeft)x=aPlatform[L].Lx;elsex=aPlatform[L].Rx;for(i=L+1;i=n;i++)//找到下一张板子{if(aPlatform[i].Lx=x&&aPlatform[i].Rx=x)break;}if(i=n)//找到了{if(y-aPlatform[i].hmax)//太高returnINFINITE;}11/283、参考程序else//没找到{if(ymax)//离地面太高returnINFINITE;elsereturny;}//特殊情况处理完毕intnLeftTime=y-aPlatform[i].h+x-aPlatform[i].Lx;intnRightTime=y-aPlatform[i].h+aPlatform[i].Rx-x;if(aLeftMinTime[i]==-1)//还没有存储值aLeftMinTime[i]=MinTime(i,true);if(aRightMinTime[i]==-1)aRightMinTime[i]=MinTime(i,false);nLeftTime+=aLeftMinTime[i];nRightTime+=aRightMinTime[i];if(nLeftTimenRightTime)returnnLeftTime;returnnRightTime;}12/283、参考程序intmain(void){scanf(%d,&t);for(inti=0;it;i++){memset(aLeftMinTime,-1,sizeof(aLeftMinTime));memset(aRightMinTime,-1,sizeof(aRightMinTime));scanf(%d%d%d%d,&n,&x,&y,&max);aPlatform[0].Lx=x;aPlatform[0].Rx=x;//长度为0的板子aPlatform[0].h=y;for(intj=1;j=n;j++)scanf(%d%d%d,&aPlatform[j].Lx,&aPlatform[j].Rx,&aPlatform[j].h);qsort(aPlatform,n+1,sizeof(Platform),MyCompare);printf(%d\n,MinTime(0,true));}return0;}思考题：重新编写此程序，要求不使用递归函数13/28最长公共子序列1、问题描述我们称序列Z=z1,z2,...,zk是序列X=x1,x2,...,xm的子序列当且仅当存在严格上升的序列i1,i2,...,ik，使得对j=1,2,...,k,有xij=zj。比如Z=a,b,f,c是X=a,b,c,f,b,c的子序列。现在给出两个序列X和Y，你的任务是找到X和Y的最大公共子序列，也就是说要找到一个最长的序列Z，使得Z既是X的子序列也是Y的子序列。•输入数据输入包括多组测试数据。每组数据包括一行，给出两个长度不超过200的字符串，表示两个序列。两个字符串之间由若干个空格隔开。14/28问题描述•输出要求对每组输入数据，输出一行，给出两个序列的最大公共子序列的长度。•输入样例abcfbcabfcabprogrammingcontestabcdmnp•输出样例42015/282、解题思路用字符数组s1、s2存放两个字符串，用s1[i]表示s1中的第i个字符，s2[j]表示s2中的第j个字符（字符编号从1开始），用s1i表示s1的前i个字符所构成的子串，s2j表示s2的前j个字符构成的子串，MaxLen(i,j)表示s1i和s2j的最长公共子序列的长度，那么递推关系如下：if(i==0||j==0)MaxLen(i,j)=0//两个空串的最长公共子序列长度是0elseif(s1[i]==s2[j])MaxLen(i,j)=MaxLen(i-1,j-1)+1;elseMaxLen(i,j)=Max(MaxLen(i,j-1),MaxLen(i-1,j));16/282、解题思路显然本题目的“状态”就是s1中的位置i和s2中的位置j。“值”就是MaxLen(i,j)。状态的数目是s1长度和s2长度的乘积。可以用一个二维数组来存储各个状态下的“值”。本问题的两个子问题，和原问题形式完全一致的，只不过规模小了一点。17/283、参考程序#includestdio.h#includestring.h#defineMAX_LEN1000charsz1[MAX_LEN];charsz2[MAX_LEN];intaMaxLen[MAX_LEN][MAX_LEN];intmain(void){while(scanf(%s%s,sz1+1,sz2+1)0){intnLength1=strlen(sz1+1);intnLength2=strlen(sz2+1);inti,j;for(i=0;i=nLength1;i++)aMaxLen[i][0]=0;for(j=0;j=nLength2;j++)aMaxLen[0][j]=0;18/283、参考程序for(i=1;i=nLength1;i++){for(j=1;j=nLength2;j++){if(sz1[i]==sz2[j])aMaxLen[i][j]=aMaxLen[i-1][j-1]+1;else{intnLen1=aMaxLen[i][j-1];intnLen2=aMaxLen[i-1][j];if(nLen1nLen2)aMaxLen[i][j]=nLen1;elseaMaxLen[i][j]=nLen2;}}}printf(%d\n,aMaxLen[nLength1][nLength2]);}return0;}19/28陪审团的人选1、问题描述在遥远的国家佛罗布尼亚，嫌犯是否有罪，须由陪审团决定。陪审团是由法官从公众中挑选的。先随机挑选n个人作为陪审团的候选人，然后再从这n个人中选m人组成陪审团。选m人的办法是：控方和辩方会根据对候选人的喜欢程度，给所有候选人打分，分值从0到20。为了公平起见，法官选出陪审团的原则是：选出的m个人，必须满足辩方总分和控方总分的差的绝对值最小。如果有多种选择方案的辩方总分和控方总分的之差的绝对值相同，那么选辩控双方总分之和最大的方案即可。最终选出的方案称为陪审团方案。20/28问题描述输入数据输入包含多组数据。每组数据的第一行是两个整数n和m，n是候选人数目，m是陪审团人数。注意，1=n=200,1=m=20而且m=n。接下来的n行，每行表示一个候选人的信息，它包含2个整数，先后是控方和辩方对该候选人的打分。候选人按出现的先后从1开始编号。两组有效数据之间以空行分隔。最后一组数据n=m=0输出要求对每组数据，先输出一行，表示答案所属的组号,如'Jury#1','Jury#2',等。接下来的一行要象例子那样输出陪审团