第9章--第3节-动态规划经典题(C--版).ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第九章 动态规划,第一节 动态规划的基本模型,第二节 背包问题,第三节 动态规划经典题,动态规划程序设计是对解最优化问题的一种途径、一种方法，而不是一种特殊算法。不象前面所述的那些搜索或数值计算那样，具有一个标准的数学表达式和明确清晰的解题方法。动态规划程序设计往往是针对一种最优化问题，由于各种问题的性质不同，确定最优解的条件也互不相同，因而动态规划的设计方法对不同的问题，有各具特色的解题方法，而不存在一种万能的动态规划算法，可以解决各类最优化问题。因此读者在学习时，除了要对基本概念和方法正确理解外，必须具体问题具体分析处理，以丰富的想象力去建立模型，用创造性的技巧去求解。我们也可以通过对若干有代表性的问题的动态规划算法进行分析、讨论，逐渐学会并掌握这一设计方法。,第四三节 动态规划经典题,【,例,9-18】,、合并石子,【,问题描述,】,在一个操场上一排地摆放着堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。,【,编程任务,】,试设计一个程序，计算出将堆石子合并成一堆的最小得分。,【,输入格式,】,第一行为一个正整数,N(2,100),；,以下行,每行一个正整数，小于,10000,，分别表示第,i,堆石子的个数,(1iN),。,【,输出格式,】,为一个正整数，即最小得分。,si,表示前,i,堆石头的价值总和，,fij,表示把第,i,堆到第,j,堆的石头合并成一堆的最优值。,for(i=n-1;i=1;i-),for(j=i+1;j=,n;j,+),for(k=,i;k,b?b:a;/,三目运算符，相当于,if(ab)return b;else return a;,int,f101101;,int,s101;,int,n,i,j,k,x,;,int main(),scanf(%d,for(i=1;i=n;i+),scanf(%d,si=si-1+x;,memset(f,127/3,sizeof(f);,/,赋值,127,是很大的正数，若无,/3,后面的相加,for(i=1;i=1;i-),for(j=i+1;j=n;j+),for(k=i;k=j-1;k+),fij=min(fij,fik+fk+1j+sj-si-1);,printf(%dn,f1n);,return 0;,【,例,9-19】,乘积最大,【,问题描述,】,今年是国际数学联盟确定的“,2000,世界数学年”，又恰逢我国著名数学家华罗庚先生诞辰,90,周年。在华罗庚先生的家乡江苏金坛，组织了一场别开生面的数学智力竞赛的活动，你的一个好朋友,XZ,也有幸得以参加。活动中，主持人给所有参加活动的选手出了这样一道题目：,设有一个长度为,N,的数字串，要求选手使用,K,个乘号将它分成,K+1,个部分，找出一种分法，使得这,K+1,个部分的乘积最大。,为了帮助选手能够正确理解题意，主持人还举了如下的一个例子：,有一个数字串：,312,，当,N=3,，,K=1,时会有以下两种分法：,1,）,3*12=36,2,）,31*2=62,这时，符合题目要求的结果是：,31*2=62,。,现在，请你帮助你的好朋友,XZ,设计一个程序，求得正确的答案。,【,输入格式,】,mul.in,第一行共有,2,个自然数,N,，,K,（,6N40,，,1K6,）,第二行是一个长度为,N,的数字串。,【,输出格式,】,mul.out,输出所求得的最大乘积（一个自然数）。,【,输入样例,】,4 2,1231,【,输出样例,】,62,【,算法分析,】,此题满足动态规划法的求解标准，我们把它按插入的乘号数来划分阶段，若插入,K,个乘号，可把问题看做是,K,个阶段的决策问题。设,fik,表示在前,i,位数中插入,K,个乘号所得的最大值，,aji,表示从第,j,位到第,i,位所组成的自然数。用,fik,存储阶段,K,的每一个状态，可以得状态转移方程：,fik,=maxfjk-1*aj+1i,（,k=j=i,）,边界值：,fj0=a1j(1j=i),根据状态转移方程，我们就很容易写出动态规划程序：,for(k,=1;k=,r;k,+)/r,为乘号个数,for(i=k+1;i=,n;i,+),for(j=,k;j,i;j,+),if(,fik,b?a:b,;,int main(),scanf(%d%d,scanf(%lld,for(i=n;i=1;i-),aii=s%10;,s/=10;,for(i=2;i=1;j-),aji=aji-1*10+aii;,for(i=1;i=n;i+)/,预处理不加乘号的情况,fi0=a1i;,for(k=1;k=k1;k+),for(i=k+1;i=n;i+),for(j=k;ji;j+),fik=max(fik,fjk-1*aj+1i);,printf(%lldn,fnk1);,return 0;,【,例,9-20】,编辑距离,【,问题描述,】,设,A,和,B,是两个字符串。我们要用最少的字符操作次数，将字符串,A,转换为字符串,B,。这里所说的字符操作共有三种：,1,、删除一个字符；,2,、插入一个字符；,3,、将一个字符改为另一个字符。,【,编程任务,】,对任的两个字符串,A,和,B,，计算出将字符串,A,变换为字符串,B,所用的最少字符操作次数。,【,输入格式,】,edit.in,第一行为字符串,A,；第二行为字符串,B,；字符串,A,和,B,的长度均小于,200,。,【,输出格式,】,edit.out,只有一个正整数，为最少字符操作次数。,【,输入样例,】,sfdqxbw,gfdgw,【,输出样例,】,4,【,算法分析,】,状态：,fij,记录,ai,与,bj,的最优编辑距离,结果：,fmn,，其中,m,、,n,分别是,a,、,b,的串长,初值：,b,串空，要删,a,串长个字符；,a,串空，要插,b,串长个字符,转移方程：当,ai,=,bj,时，,fij,=fi-1j-1,，否则，,fij,=min(fi-1j-1+1,fij-1+1,fi-1j+1),说明：,fi-1j-1+1,：改,ai,为,bj,；,fij-1+1,：,ai,后插入,bj-1,；,fi-1j+1,：删,ai,。,【,参考程序,】,#include,#include,int,min(int,a,int,b)return,a,b?a:b,;,int,f202202;,char s1202,s2202;,int,i,j,k,m,n,;,int,main(),scanf(%s%s,s1,s2);,m=strlen(s1);,n=strlen(s2);,for(i=1;i=,m;i,+)fi0=i;/,到,i,位置为止把字符串,A,的内容全部删除,for(i=1;i=,n;i,+)f0i=i;/,在开头给字符串,A,添上和,B,到,i,位置相同的字符,for(i=1;i=m;i+),for(j=1;j=n;j+),if(s1i-1=s2j-1)fij=fi-1j-1;,else fij=min(min(fi-1j,fij-1),fi-1j-1)+1;,printf(%dn,fmn,);,return 0;,【,例,9-21】,方格取数,【,问题描述,】,设有,NN,的方格图，我们在其中的某些方格中填入正整数，而其它的方格中则放入数字,0,。如下图所示：,某人从图中的左上角的,A,出发，可以向下行走，也可以向右行走，直到达右下角的,B,点。在走过的路上，他可以取走方格中的数,(,取走后的方格中将变为数字,0),。,【,编程任务,】,此人从,A,点到,B,点共走了两次，试找出两条这样的路径，使得取得的数字和为最大。,【,输入格式,】,Pane.in,输入文件,Pane.in,第一行为一个整数,N,（,N10,），表示,NN,的方格图。,接下来的每行有三个整数，第一个为行号数，第二个为列号数，第三个为在该行、该列上所放的数。一行,0 0 0,表示结束。,【,输出格式,】,Pane.out,输出文件,Pane.out,包含一个整数，表示两条路径上取得的最大的和。,【,输入样例,】,8,2 3 13,2 6 6,3 5 7,4 4 14,5 2 21,5 6 4,6 3 15,7 2 14,0 0 0,【,输出样例,】,67,【,算法分析,】,一个四重循环枚举两条路分别走到的位置。由于每个点均从上或左继承而来，故内部有四个,if,，分别表示两个点从上上、上左、左上、左左继承来时，加上当前两个点所取得的最大值。,aij,表示,(,i,j,),格上的值，,sumijhk,表示第一条路走到,(,i,j,),，第二条路走到,(,h,k,),时的最优解。例如，,sumijhk,=,maxsumijhk,sumi-1jh-1k+,aij,+,ahk,，表示两点均从上面位置走来。,当,(,i,j,)(,h,k,),）时,sumijhk,:=maxsumi-1jh-1k,sumij-1hk-1,sumi-1jhk-1,sumij-1h-1k+aij+ahk;,当,(,i,j,)=(,h,k,),时,sumijhk,:=maxsumi-1jh-1k,sumij-1hk-1,sumi-1jhk-1,sumij-1h-1k+aij;,【,参考程序,1】,#include,int,max(int,a,int,b)return,a,b?a:b,;,int,a5151;,int,sum51515151;,int,n,i,j,h,k,x,y,z,;,int main(),scanf(%d%d%d%d,while(x&y&z)/C+,中大于,0,的正整数都看作,true,，只有,0,看作,false,axy=z;,scanf(%d%d%d,for(i=1;i=n;i+),for(j=1;j=n;j+),for(h=1;h=n;h+),for(k=1;k=n;k+),int,tmp1=max(sumi-1jh-1k,sumij-1hk-1);,int,tmp2=max(sumi-1jhk-1,sumij-1h-1k);,sumijhk=max(tmp1,tmp2)+aij;,if(i!=h,printf(%dn,sumnnnn);,return 0;,【,例,9-22】,复制书稿,(,book.pas,),【,问题描述,】,现在要把,m,本有顺序的书分给,k,个人复制（抄写），每一个人的抄写速度都一样，一本书不允许给两个（或以上）的人抄写，分给每一个人的书，必须是连续的，比如不能把第一、第三和第四本书给同一个人抄写。,现在请你设计一种方案，使得复制时间最短。复制时间为抄写页数最多的人用去的时间。,【,输入格式,】,第一行两个整数,m,，,k,；（,km500,）,第二行,m,个整数，第,i,个整数表示第,i,本书的页数。,【,输出格式,】,共,k,行，每行两个整数，第,i,行表示第,i,个人抄写的书的起始编号和终止编号。,k,行的起始编号应该从小到大排列，如果有多解，则尽可能让前面的人少抄写。,【,输入输出样例,】,book.in,book.out,9 31 5,1 2 3 4 5 6 7 8 96 7,8 9,【,问题分析,】,本题可以用动态规划解决，设,f(k,m,),为前,m,本书交由,k,个人抄写，需要的最短时间，则状态转移方程为,fkm,=minmaxfk-1i,i=1,2,m-1,动态规划求出的仅仅是最优值，如果要输出具体方案，还需根据动态规划计算得到的最优值，做一个贪心设计。具体来说，设最优值为,T,，那么,k,个人，每个人抄写最多,T,页。从最后一本书开始按逆序将书分配给,k,人去抄写，从第,k,个人开始，如果他还能写，就给他；否则第,k,个人工作分配完毕，开始分配第,k-1,个人的工作；以后再是第,k-2,个、第,k-3,个、,直至第,1,个。一遍贪心结束后，具体的分配方案也就出来了。,【,参考程序,】,#include,#include,#include,using namespace std;,int,max1(int,int);,int,print(int,int,);,int,x,y,i,j,m,n,k,t,l,;,int,a501,f501501,d501;,int,main(),cin,mk;,for(i=0;i=500;i+),for(j=0;j=500;j+),fij,=10000000;,for(j=1;j,aj,;/,输入,m,本书的页数,dj,=dj-1+aj;/,dj,为前,j,本书总的页数,f1j=,dj,;/,fij,为一个人抄前,j,本书所需时间,for(i=2;i=,k;i,+)/,fkm,为前,m,本书交由,k,个人抄写，需要的最短时间,for(j=1;j=,m;j,+),for(l=1;l=j-1;l+),if(max1(fi-1l,dj-dl)y)return x;else return y;,int,print(int,i,int,j)/,递归输出抄写页数的方案,int,t,x,;,if(j=0)return 0;,if(j=1)/,第,1,个人抄写,1,到,i,本书,cout,1 i,endl,;,return 0;,t=,i;x,=,ai,;,while(x+at-1=,fkm,),/,从最后一本书按逆序分配第,j,个人抄写，只要能写，就给他,x+=at-1;,t-;,print(t-1,j-1);/,用递归过程给第,j-1,个人分配抄写方案，这时只有,t-1,书了,cout,t i,endl,;/,递归返回时输出，因为递归过程是最后,1,个人先分配抄书,【,例题,9-23】,橱窗布置（,Flower,）,【,问题描述,】,假设以最美观的方式布置花店的橱窗，有,F,束花，每束花的品种都不一样，同时，至少有同样数量的花瓶，被按顺序摆成一行，花瓶的位置是固定的，并从左到右，从,1,到,V,顺序编号，,V,是花瓶的数目，编号为,1,的花瓶在最左边，编号为,V,的花瓶在最右边，花束可以移动，并且每束花用,1,到,F,的整数惟一标识，标识花束的整数决定了花束在花瓶中列的顺序即如果,I J,，则花束,I,必须放在花束,J,左边的花瓶中。,例如，假设杜鹃花的标识数为,1,，秋海棠的标识数为,2,，康乃馨的标识数为,3,，所有的花束在放人花瓶时必须保持其标识数的顺序，即：杜鹃花必须放在秋海棠左边的花瓶中，秋海棠必须放在康乃馨左边的花瓶中。如果花瓶的数目大于花束的数目，则多余的花瓶必须空，即每个花瓶中只能放一束花。,每一个花瓶的形状和颜色也不相同，因此，当各个花瓶中放人不同的花束时会产生不同的美学效果，并以美学值,(,一个整数,),来表示，空置花瓶的美学值为,0,。在上述例子中，花瓶与花束的不同搭配所具有的美学值，可以用如下表格表示。,根据表格，杜鹃花放在花瓶,2,中，会显得非常好看，但若放在花瓶,4,中则显得很难看。,为取得最佳美学效果，必须在保持花束顺序的前提下，使花的摆放取得最大的美学值，如果具有最大美学值的摆放方式不止一种，则输出任何一种方案即可。题中数据满足下面条件：,1F100,，,FV100,，,50A,IJ,50,，其中,A,ij,是花束,I,摆放在花瓶,J,中的美学值。输入整数,F,，,V,和矩阵,(A,IJ,),，输出最大美学值和每束花摆放在各个花瓶中的花瓶编号。,花瓶,1 ,花瓶,2,花瓶,3 ,花瓶,4,花瓶,5 ,杜鹃花,7 23 -5 -24 16 ,秋海棠,5 21 -4 10 23 ,康乃馨,-21 5 -4 -20 20 ,1,、假设条件,1F100,，其中,F,为花束的数量，花束编号从,1,至,F,。,FV100,，其中,V,是花瓶的数量。,-50A,ij,50,，其中,A,ij,是花束,i,在花瓶,j,中的美学值。,2,、输入,输入文件是,flower.in,。,第一行包含两个数：,F,，,V,。,随后的,F,行中，每行包含,V,个整数，,A,ij,即为输入文件中第（,i+1,）行中的第,j,个数。,3,、输出,输出文件必须是名为,flower.out,的正文文件，文件应包含两行：,第一行是程序所产生摆放方式的美学值。,第二行必须用,F,个数表示摆放方式，即该行的第,K,个数表示花束,K,所在的花瓶的编号。,【,样例输入,】,3 5,7 23 5 24 16,5 21-4 10 23,-21 5-4-20 20,【,样例输出,】,53,2 4 5,【,解法一,】,【,算法分析,】,问题实际就是给定,F,束花和,V,个花瓶，以及各束花放到不同花瓶中的美学值，要求你找出一种摆放的方案，使得在满足编号小的花放进编号小的花瓶中的条件下，美学值达到最大。,将问题进行转化，找出问题的原型。首先，看一下上述题目的样例数据表格。,将摆放方案的要求用表格表现出来，则摆放方案需要满足：每行选且只选一个数,(,花瓶,),；摆放方案的相邻两行中，下面一行的花瓶编号要大于上面一行的花瓶编号两个条件。这时可将问题转化为：给定一个数字表格，要求编程计算从顶行至底行的一条路径，使得这条路径所经过的数字总和最大,(,要求每行选且仅选一个数字,),。同时，路径中相邻两行的数字，必须保证下一行数字的列数大于上一行数字的列数。,看到经过转化后的问题，发现问题与“数学三角形”问题十分相似，数字三角形问题的题意是：,给定一个数字三角形，要求编程计算从顶至底的一条路径，使得路径所经过的数字总和最大,(,要求每行选且仅选一个数字,),。同时，路径中相邻两行的数字，必须保证下一行数字的列数与上一行数字的列数相等或者等于上一行数字的列数加,1,。,上例中已经知道：数字三角形中的经过数字之和最大的最佳路径，路径的每个中间点到最底层的路径必然也是最优的，可以用动态规划方法求解，对于“花店橱窗布置”问题经过转化后，也可采取同样的方法得出本题同样符合最优性原理。因此，可以对此题采用动态规划的方法。,【,参考程序,】,#include,#include,#include,using namespace std;,int,main(),int,a101101,b101101,c101101,d101;/,aij,花束,i,放在花瓶,j,中的美学值,/,bij,前,i,束花放在前,j,个花瓶中的最优解,/cij,在,bij,的最优解中，花束,i-1,的位置,int f,v,i,j,k,max;,/f,v,花束和花瓶的数目,cinfv;,for(i=1;i=f;i+),for(j=1;jaij;,memset(b,128,sizeof(b);/,这样处理，可以保证每束花都放进花瓶,for(i=1;i=v-f+1;i+),/,初始化第,1,束花放在第,i,个花瓶的情况,b1i=a1i;,for(i=2;i=f;i+),for(j=i;j=v-f+i;j+),for(k=i-1;kbij),bij=bi-1k+aij;/,更新当前最优解,cij=k;/,前一个花束的位置为,k,max=-2100000000;,for(i=f;imax),max=bfi;/,选择全局最优解,k=i;/k,最后一束花的位置,coutmaxendl;/,打印最优解,for(i=1;i=2;i-),cout,di,;,coutd1endl;,由此可看出，对于看似复杂的问题，通过转化就可变成简单的经典的动态规划问题。在问题原型的基础上，通过分析新问题与原问题的不同之处，修改状态转移方程，改变问题状态的描述和表示方式，就会降低问题规划和实现的难度，提高算法的效率。由此可见，动态规划问题中具体的规划方法将直接决定解决问题的难易程度和算法的时间与空间效率，而注意在具体的规划过程中的灵活性和技巧性将是动态规划方法提出的更高要求。,【,解法二,】,【,算法分析,】,flower,一题是,IOI99,第一天第一题，该题如用组合的方法处理，将会造成超时。正确的方法是用动态规划，考虑角度为一束一束地增加花束，假设用,bij,表示,1,i,束花放在,1,到,j,之间的花瓶中的最大美学值，其中,i=j,，则,bij,=max(bi-1k-1+Aik),，其中,i=k=j,，,Aik,的含义参见题目。输出结果时，显然使得,bFk,取得总的最大美观值的第一个,k,值就是第,F,束花应该摆放的花瓶位置，将总的最大美观值减去,Aik,的值即得到前,k-1,束花放在前,k-1,个瓶中的最大美观值，依次使用同样的方法就可求出每一束花应该摆放的花瓶号。由于这一过程是倒推出来的，所以程序中用递归程序来实现。,【,参考程序,】,#include,#include,#include,using namespace std;,void,print(int,int,);,int,max(int,a,int,b)return a,b?a:b,;,int,a101101,b101101;,int,main(),int,f,v,;,cin,fv;,for(,int,i=1;i=,f;i,+),for(,int,j=1;j,aij,;,memset(b,128,sizeof(b);/,初始化,b,数组,for(,int,i=0;i101;i+)b0i=0 /,没有放花时，美学值为,0,。这也是初始化,for(,int,i=1;i=,f;i,+),for(,int,j=,i;j,=,v-f+i;j,+),for(,int,k=,i;k,=,j;k,+),bij=max(bij,bi-1k-1+aik);,int,c=-1000000;,for(,int,i=,f;i,c),c=,bfi,;,coutc0),n=i;,while(,bin,!=j),n+;,print(i-1,j-ain);,cout,n;,记忆化搜索的应用,一般来说，动态规划总要遍历所有的状态，而搜索可以排除一些无效状态。更重要的是搜索还可以剪枝，可能剪去大量不必要的状态，因此在空间开销上往往比动态规划要低很多。,如何协调好动态规划的高效率与高消费之间的矛盾呢？有一种折中的办法就是记忆化算法。记忆化算法在求解的时候还是按着自顶向下的顺序，每求解一个状态，就将它的解保存下来，以后再次遇到这个状态的时候，就不必重新求解了。这种方法综合了搜索和动态规划两方面的优点，因而还是很有使用价值的。举一个例子：如下图所示是一个有向无环图，求从顶点,1,到顶点,6,的最长路径。（规定边的方向从左到右）,我们将从起点（顶点,1,）开始到某个顶点的最长路径作为状态，用一维数组,opt,记录。,Optj,表示由起点到顶点,j,时的最长路径。显然，,opt1=0,，这是初始状态，即动态规划的边界条件。于是，我们很容易地写出状态转移方程式：,optj,=,maxoptk+akj,（,k,到,j,有一条长度为,akj,的边）。虽然有了完整的状态转移方程式，但是还是不知道动态规划的顺序。所以，还需要先进行一下拓扑排序，按照排序的顺序推下去，,opt6,就是问题的解。,可以看出，动态规划相比搜索之所以高效，是因为它将所有的状态都保存了下来。当遇到重复子问题时，它不像搜索那样把这个状态的最优值再计算一遍，只要把那个状态的最优值调出来就可以了。例如，当计算,opt4,和,opt5,时，都用到了,opt3,的值。因为已经将它保存下来了，所以就没有必要再去搜索了。,但是动态规划仍然是有缺点的。一个很突出的缺点就是要进行拓扑排序。这道题的拓扑关系是很简单的，但有些题的拓扑关系是很复杂的。对于这些题目，如果也进行拓扑排序，工作量非常大。遇到这种情况，我们可以用记忆化搜索的方法，避免拓扑排序。,【,例,9-24】,滑雪,【,问题描述,】,小明喜欢滑雪，因为滑雪的确很刺激，可是为了获得速度，滑的区域必须向下倾斜，当小明滑到坡底，不得不再次走上坡或等着直升机来载他，小明想知道在一个区域中最长的滑坡。滑坡的长度由滑过点的个数来计算，区域由一个二维数组给出，数组的每个数字代表点的高度。下面是一个例子：,1 2 3 4 5,16 17 18 19 6,15 24 25 20 7,14 23 22 21 8,13 12 11 10 9,一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度减小，在上面的例子中，一条可行的滑坡为,25-24-17-16-1,（从,25,开始到,1,结束），当然,25-2421,更长，事实上这是最长的一条。,【,输入格式,】,输入的第一行为表示区域的二维数组的行数,R,和列数,C,（,1R,、,C100,）下面是,R,行，每行有,C,个数代表高度。,【,输出格式,】,输出区域中最长的滑坡长度。,i-1,j,i,j-1,i,j,i,j+1,i+1,j,【,输入样例,】,ski.in,5 5,1 2 3 4 5,16 17 18 19 6,15 24 25 20 7,14 23 22 21 8,13 12 11 10 9,【,输出样例,】,ski.out,25,【,算法分析,】,由于一个人可以从某个点滑向上下左右相邻四个点之一，如上图所示。当且仅当高度减小，对于任意一个点,i,j,，当它的高度小于与之相邻的四个点（,i-1,j,i,j+1,i+1,j,i,j-1,）的高度时，这四个点可以滑向,i,j,，用,fij,表示到,i,j,为止的最大长度，则,fij,=maxfi+aj+b+1,，其中坐标增量,(,a,b,)=(1,0),(-1,0),(0,1),(0,-1),0,i+a,=r,，,0,j+b,=c,，,Highij,Highi+aj+b,。为了保证满足条件的,fi+aj+b,在,fij,前算出，需要对高度排一次序，然后从大到小规划（高度）。最后再比较一下所有,fij0ir,0,jc,，找出其中最长的一条路线。我们还可以用记忆化搜索的方法，它的优点是不需进行排序，按照行的顺序，利用递归逐点求出区域中到达此点的最长路径，每个点的最长路径只求一次。,【,参考程序,】,#include,#include,using namespace std;,int,dx5=0,-1,0,1,0,/x,的坐标增量,dy5=0,0,1,0,-1;/y,的坐标增量,long,r,c,i,j,p,t,ans,;,long m101101,f101101;,int,search(int,int,);,int main(),cinrc;,ans=0;,for(i=1;i=r;i+),for(j=1;jmij;/,读入每个点的高度,for(i=1;i=r;i+)/,按照行的顺序，利用递归逐点求出区域中到达此点的最长路径,for(j=1;jans)ans=t;/,寻找最大长度值,coutans0),/,此点长度已经求出，不必进行进一步递归，保证每,/,一个点的最大长度只求一次，这是记忆化搜索的特点,return(,fxy,);,t=1;,for(i=1;i=1)&(nx=1)&(ny=,c)&(mxy,t)t=,tmp,;,fxy,=t;,return(t);,【,上机练习,】,1,、防卫导弹,(,Catcher.pas,),【,问题描述,】,一种新型的防卫导弹可截击多个攻击导弹。它可以向前飞行，也可以用很快的速度向下飞行，可以毫无损伤地截击进攻导弹，但不可以向后或向上飞行。但有一个缺点，尽管它发射时可以达到任意高度，但它只能截击比它上次截击导弹时所处高度低或者高度相同的导弹。现对这种新型 防卫导弹进行测试，在每一次测试中，发射一系列的测试导弹（这些导弹发射的间隔时间固定，飞行速度相同），该防卫导弹所能获得的信息包括各进攻导弹的高度，以及它们发射次序。现要求编一程序，求在每次测试中，该防卫导弹最多能截击的进攻导弹数量，一个导弹能被截击应满足下列两个条件之一：,1,、它是该次测试中第一个被防卫导弹截击的导弹；,2,、它是在上一次被截击导弹的发射后发射，且高度不大于上一次被截击导弹的高度的导弹。,【,输入格式,】,从当前目录下的文本文件“,CATCHER.IN”,读入数据。该文件的第一行是一个整数,N(0=N=4000),，表示本次测试中，发射的进攻导弹数，以下,N,行每行各有一个整数,hi(0=hi=32767),，表示第,i,个进攻导弹的高度。文件中各行的行首、行末无多余空格，输入文件中给出的导弹是按发射顺序排列的。,【,输出格式,】,答案输出到当前目录下的文本文件“,CATCHER.OUT”,中，该文件第一行是一个整数,max,，表示最多能截击的进攻导弹数，以下的,max,行每行各有一个整数，表示各个被截击的进攻导弹的编号（按被截击的先后顺序排列）。输出的答案可能不唯一，只要输出其中任一解即可。,【,输入输出样例,】,输入文件：,CATCHER.IN,输出文件：,CATCHER.OUT,3,2,25,1,36,3,23,2,、拔河比赛,(,tug.pas,),【,问题描述,】,一个学校举行拔河比赛，所有的人被分成了两组，每个人必须（且只能够）在其中的一组，要求两个组的人数相差不能超过,1,，且两个组内的所有人体重加起来尽可能地接近。,【,输入格式,】,输入数据的第,1,行是一个,n,，表示参加拔河比赛的总人数，,n=100,，接下来的,n,行表示第,1,到第,n,个人的体重，每个人的体重都是整数（,1=weight=450,）,【,输出格式,】,输出数据应该包含两个整数：分别是两个组的所有人的体重和，用一个空格隔开。注意如果这两个数不相等，则请把小的放在前面输出。,【,输入样例,】,tug.in,3,100,90,200,【,输出样例,】,tug.out,190 200,3,、求最短距离,(,distance.pas,),【,问题描述,】,小雨家住在小区里。她今年上小学一年级。每天她都要走路去车站，然后坐车去上学。小区被道路分成许多正方形的块，共,N*M,块。由于道路太多，她总是迷路。作为程序高手，你帮小雨计算一下从她家到达车站的最短距离。注意。一般情况下，小区内的方块建有房屋，只能沿着附近的街道行走，有时方块表示公园，那么就可以直接穿过。样例如下图所示。,【,输入格式,】,第一行是,N,和,M(0N,M1000,。注意，小雨家的坐标在方块,(1,1),的西南角，车站在方块,(M,N),的东北角。每个方块边长,100,米。接下来一行是整数,k,，表示可以对角线穿过的方块坐标。然后有,k,行，每行是一个坐标。,车站小雨家,【,输出格式,】,输出从小雨家到车站的最短距离，四舍五入到整数（米）。,【,输入样例,】,distance.in,3 2,3,1 1,3 2,1 2,【,输出样例,】,distance.out,383,4,、机器分配,(,assigned.pas,),【,问题描述,】,总公司拥有高效设备,M,台，准备分给下属的,N,个分公司。各分公司若获得这些设备，可以为国家提供一定的盈利。问：如何分配这,M,台设备才能使国家得到的盈利最大？求出最大盈利值。其中,M15,，,N10,。分配原则：每个公司有权获得任意数目的设备，但总台数不超过设备数,M,。,输入数据文件格式为：第一行有两个数，第一个数是分公司数,N,，第二个数是设备台数,M,。,接下来是一个,N*M,的矩阵，表明了第,I,个公司分配,J,台机器的盈利。,【,输入样例,】,assigned.in,3 3 /3,个分公司分,3,台机器,30 40 50,20 30 50,20 25 30,【,输出样例,】,assigned.out,70 /,最大盈利值为,70,1 1 /,第一分公司分,1,台,2 1 /,第二分公司分,1,台,3 1 /,第三分公司分,1,台,5,、复制书稿,(,book.pas,),【,问题描述,】,现在要把,m,本有顺序的书分给,k,给人复制（抄写），每一个人的抄写速度都一样，一本书不允许给两个（或以上）的人抄写，分给每一个人的书，必须是连续的，比如不能把第一、第三、第四本书给同一个人抄写。,现在请你设计一种方案，使得复制时间最短。复制时间为抄写页数最多的人用去的时间。,【,输入格式,】,第一行两个整数,m,，,k,；（,km500,）,第二行,m,个整数，第,i,个整数表示第,i,本书的页数。,【,输出格式,】,共,k,行，每行两个整数，第,i,行表示第,i,个人抄写的书的起始编号和终止编号。,k,行的起始编号应该从小到大排列，如果有多解，则尽可能让前面的人少抄写。,【,输入输出样例,】,book.in,book.out,9 31 5,1 2 3 4 5 6 7 8 96 7,8 9,6,、投资问题,(,invest.pas,),【,问题描述,】,现在有,m,个可投资项目，有,n,万元的资金，其中,m,和,n,为小于,100,的自然数。对第,i,（,1im,）个项目投资,j,万元,(1jn,，且,j,为整数,),可获得的回报为,Q,（,i,j,），请你编一个程序，求解并输出最佳的投资方案（即获得回报总值最高的投资方案）。,【,输入格式,】,m n,Q(1,0)Q(1,1)Q(1,n),Q(2,0)Q(2,1)Q(2,n),Q(m,0)Q(m,1),Q(m,n,),【,输出格式,】,r(1)r(2),r(m,)P,其中,r(i,),（,1im,）表示对第,i,个项目的投资万元数，,P,为总的投资回报值，保留两位有效数字，任意两个数之间空一格。当存在多个并列的最佳投资方案时，只要求输出其中之一即可。,【,输入样例,】,invest.in,2 3,0 1.1 1.3 1.9,0 2.1 2.5 2.6,【,输出样例,】,invest.out,1 2 3.6,7,、潜水员,【,问题描述,】,潜水员为了潜水要使用特殊的装备。他有一个带,2,种气体的气缸：一个为氧气，一个为氮气。让潜水员下潜的深度需要各种的数量的氧和氮。潜水员有一定数量的气缸。每个气缸都有重量和气体容量。潜水员为了完成他的工作需要特定数量的氧和氮。他完成工作所需气缸的总重的最低限度的是多少？,例如：潜水员有,5,个气缸。每行三个数字为：氧，氮的（升）量和气缸的重量：,3 36 120,10 25 129,5 50 250,1 45 130,4 20 119,如果潜水员需要,5,升的氧和,60,升的氮则总重最小为,249,（,1,，,2,或者,4,，,5,号气缸）。,你的任务就是计算潜水员为了完成他的工作需要的气缸的重量的最低值。,【,输入格式,】,第一行有,2,整数,t,，,a,（,1=t=21,，,1=a=79,）。它们表示氧，氮各自需要的量。,第二行为整数,n,（,1=n=1000,）表示气缸的个数。,此后的,n,行，每行包括,ti,，,ai,，,wi,（,1=,t,i,=21,，,1=,a,i,=79,，,1=,w,i,=800,）,3,整数。这些各自是：第,i,个气缸里的氧和氮的容量及汽缸重量。,【,输出格式,】,仅一行包含一个整数，为潜水员完成工作所需的气缸的重量总和的最低值。,【,输入样例,】,5 60,5,3 36 120,10 25 129,5 50 250,1 45 130,4 20 119,【,输出样例,】,249,8,、火车票,【,问题描述,】,从,Ekaterinburg,到,Sverdlovsk,的火车线路上有若干个站点。这条线路可以近似的表示为一条线段，火车站就是线段上的点。线路始于,Ekaterinburg,，终于,Sverdlovsk,。,Ekaterinburg,被标号为,1,，,Sverdlovsk,被标号为,n,。（,n,为整条线路上的站点数）,线路上的任意两个站点间的直达票价是由它们间的距离决定的，票价根据以下规则制定：,X,为两站的距离,价格,0X=L1,C1,L1X=L2,C2,L2X=L3,C3,如果两站的间距超过,L3,，则无直达车票。所以有时可能有必要买多张票，通过转车的方式，从一个站到达另一个站。,例如，在上面的图中，有,7,个站点。,2,号站点到,6