动态规划教材

1、动态规划一、动态规划简介动态规划是运筹学的一个分支。它是解决多阶段决策过程最优化问题的一种 方法。1951年，美国数学家贝尔曼(R.Bellman)提出了解决这类问题的“最优 化原则”，1957年发表了他的名著动态规划，该书是动态规划方面的第一本 著作。动态规划问世以来，在工农业生产、经济、军事、工程技术等许多方面都 得到了广泛的应用，取得了显著的效果。动态规划运用于信息学竞赛是在90年代初期，它以独特的优点获得了出题 者的青睐。此后，它就成为了信息学竞赛中必不可少的一个重要方法，几乎在所 有的国内和国际信息学竞赛中，都至少有一道动态规划的题目。所以，掌握好动 态规划，是非常重要的。动态规划是

2、一种方法，是考虑问题的一种途径，而不是一种算法。因此，它 不像深度优先和广度优先那样可以提供一套模式。它必须对具体问题进行具体分 析。需要丰富的想象力和创造力去建立模型求解。二、动态规划的几个基本概念想要掌握好动态规划，首先要明白几个概念：阶段、状态、决策、策略、指 标函数。阶段：把所给问题的过程，恰当地分为若十个相互联系的阶段，以便能按一 定的次序去求解。描述阶段的变量称为阶段变量。状态：状态表示每个阶段开始所处的自然状况和客观条件，它描述了研究问 题过程中的状况，又称不可控因素。决策：决策表示当过程处于某一阶段的某个状态时，可以作出不同的决定(或 选择)，从而确定下一阶段的状态，这种决定称

3、为决策，在最优控制中也称为 控制。描述决策的变量，称为决策变量。策略：由所有阶段的决策组成的决策函数序列称为全过程策略，简称策略。状态转移方程：状态转移方程是确定过程由一个状态到另一个状态的演变过 程。指标函数：用来衡量所实现过程优劣的一种数量指标，称为指标函数。指标 函数的最优值，称为最优值函数。三、确定动态规划的思路1、采用动态规划来解决问题，必须符合两个重要的条件。“过去的历史只能通过当前状态去影响它未来的发展，当前的状态是对以往 历史的一个总结”，这种特性称为无后效性，是多阶段决策最优化问题的特征。作为整个过程的最优策略具有这样的性质：即无论过去的状态和决策如何， 对前面的决策所形成的

4、状态而言，余下的诸决策必须构成最优策略。简言之，一 个最优策略的子策略总是最优的。这就是最优化原理。2、如果碰到一个问题，能够满足以上两个条件的话，那么就可以去进一步考虑如何去设计使用动态规划：（1）划分阶段。把一个问题划分成为许多阶段来思考（2）设计合适的状态变量（用以递推的角度）（3）建立状态转移方程（递推公式）（4）寻找边界条件（已知的起始条件）如果以上几个步骤都成功完成的话，我们就可以进行编程了。四、动态规划解题的一些技巧由于动态规划并没有一个定式，这就需要去开拓我们创造力去构造并且使用 它。以下，通过一些具体的竞赛实例谈谈使用动态规划过程中的一些技巧。数塔问题:有形如图1.3-8所示

5、的数塔，从顶部出发，在每一结点可以选择向左走或是向右 走，一起走到底层，要求找出一条路径，使路径上的值最大。19710 416图 1.3-8这道题如果用枚举法，在数塔层数稍大的情况下（如40），则需要列举出的路径 条数将是一个非常庞大的数目。如果用贪心法又往往得不到最优解。在用动态规划考虑数塔问题时可以自顶向下的分析，自底向上的计算。从顶点出 发时到底向左走还是向右走应取决于是从左走能取到最大值还是从右走能取到 最大值，只要左右两道路径上的最大值求出来了才能作出决策。同样的道理下一 层的走向又要取决于再下一层上的最大值是否已经求出才能决策。这样一层一层 推下去，直到倒数第二层时就非常明了。如数

6、字2,只要选择它下面较大值的结 点19前进就可以了。所以实际求解时，可从底层开始，层层递进，最后得到最 大值。实际求解时应掌握其编程的一般规律，通常需要哪几个关键数组来存储变化过程 这一点非常重要。数塔问题的样例程序如下：var a:array1.50,1.50,1.3 of longint;第一维记原状态，第二维参与计算，第三维记录决策，0向左，1向右。浪费啊， 不如开三个一维，或三元组（指针处理麻烦，类似三角矩阵存储） i,j,n:integer;beginwrite（ please input the number of rows:）;readln（n）;for i:=1 to n do

7、for j: = 1 to i do 行元素数等于行数beginread（ai,j,1）;ai,j,2:=ai,j,1;ai,j,3:二0end;计算=for i:=n-1 downto 1 do 行选择（始于倒数第二行），阶段for j: = 1 to i do 列选择，状态if ai+1,j,2ai+1,j+1,2 then 左强begin ai,j,2:=ai,j,2+ai+1,j,2;累 计结果 （父 + 左）ai,j,3:二0 记录决策（选左）endelse右强begin ai,j,2:=ai,j,2+ai+1,j+1,2; （累 计结果（父 + 右）ai,j,3:二1记录决策（选右

8、） end;=二输出=writeln（max=,a1,1,2）;最大值j: = 1;for i:=1 to n-1 dobeginwrite（ai,j,1,-）;j:=j+ai,j,3end;writeln(an,j,1) end.总结：此题是最为基础的动态规划题目，阶段，状态 的划分一目了然。而决策的记录，充分体现了动态规划即“记忆 化搜索”的本质。最短路径问题B1-C2B20304现在，我们想从城市a到达城市E。怎样走才能使得路径最短，最短路径的长度 是多少？设DiS x为城市x到城市E的最短路径长度（x表示任意一个城市）；mapi，j表示i，j两个城市间的距离，若mapi，j=0，则两个

9、城市不通；我们可以使用回溯法来计算DiS x：varS：未访问的城市集合；function search(who(x)： integer；的最短距离beginif Who = E Then Search0求城市who与城市E找到目标城市Else beginminmaxint ；初始化最短路径为最大下图给出了一个地图，地图中每个顶点代表一个城市，两个城市间的连线代表道 路，连线上的数值代表道路长度。for i取遍所有城市Doif (mapWho, i 0(有路) and (i S 未访问) then begin置访问标志（累加城市E至城市Who的路径长度（回溯后，恢复城市i未访问状态（如果最短则

10、记下（返回最短路径长度（计算最短路径长度S-Si；jmapWho, i+ search(i)；S-S+i；if jVmin Then min-j；end； (thensearchmin；End； (elseEnd； (searchbeginS除E外的所有城市；Disa search (a)；输出 Disa；end. (main 这个程序的效率如何呢？我们可以看到，每次除了已经访问过的城市外，其他城 市都要访问，所以时间复杂度为O （n!）,这是一个“指数级”的算法。那么， 还有没有效率更高的解题方法呢？首先，我们来观察上述算法。在求bl到E的最短路径的时候，先求出从C2到E 的最短路径；而在求

11、从b2刭E的最短路径的时候，又求了一遍从C2刭E的最短 路径。也就是说，从C2到E的最短路径求了两遍。同样可以发现，在求从Cl、 C2刭E的最短路径的过程中，从Dl到E的最短路径也被求了两遍。而在整个程 序中，从Dl到E的最短路径被求了四遍，这是多么大的一个浪费啊！如果在求 解的过程中，同时将求得的最短路径的距离“记录在案”，以便将来随时调用， 则可以避免这种重复计算。至此，一个新的思路产生了，即 由后往前依次推出每个Dis值，直到推出Disa为止。问题是，究竟什么是“由后往前”呢？所谓前后关系是指对于任意一对城市i 和j来说，如果满足“或者城市i和城市j不连通或者disi+mapi，j Nd

12、isj ” 的条件，则定义为城市i在前、城市j在后。因为如果城市i和城市j连通且 Disi+mapi，jVDisj，则说明城市j至城市E的最短路径长度应该比 Disj更优。可城市j位于城市i后不可能推出此情况，以至于影响最后的解。 那么，我们应该如何划分先后次序呢？3/Z 盼段0阶段1阶段3粉段4如上图所示，从城市a出发，按照与城市a的路径长度划分阶段。阶段0包含的出发城市有a阶段1所含的城市有bl，b2阶段2包含的出发城市有Cl，C2, C3, C4阶段3包含的出发城市有Dl，D2, D3阶段4包含城市E这种划分可以明确每个城市的次序，因为阶段的划分具有如下性质阶段i的取值只与阶段i+1有关

13、，阶段i+1的取值只对阶段i的取值产生影响:每个阶段的顺序是确定的，不可以调换任两个阶段的顺序；我们从阶段4的城市E出发，按照阶段的顺序倒推至阶段0的城市a。在求解的各个阶段，利用了灯阶段与k+Ld阶段之间的如下关系X, y) g Gdiskx= yGk+1阶段的城市集”dis4E=0k=4, 3，0，其中diskx指k阶段的城市x。由此得出程序disE-0；for k3 downto 0 do倒序枚举阶段for x取遍k阶段的所有城市dobegindisx -8；初始化最短路径为最大for y 取遍 k+1 阶段的所有城市 do if disy+mapx,yhi)为最佳方案，则记下hi hj

14、+1； wi j；end； (then(调整一套系统if hibest能拦截的最多导数then begin besthi ； one i； end； (then end；(for输出当前系统拦截的最多导弹系数best；3、按照求解途径给出当前系统拦截的导弹序列我们在计算拦截最多导弹数的过程中，利用记忆表w和one来确定拦截的最 佳方式。每一项wi记录了拦截导弹i之后应拦截哪一枚导弹可取得hi,而 最佳方案中拦截的第一枚导弹为one。由此可知，最佳拦截次序应为onef wone f wwonef i(i=wi)。从导弹one出发，按照w表的指引，依次输出当前 系统拦截的导弹序列：while on

15、e#wonedobegin输出导弹one被拦截；onewone；end； (while口 ，输出导弹one被拦截；搬砖问题一个小孩有N块砖，他可以用这些砖建造不同的楼梯。楼梯由大小严格递减的台 阶组成，不允许有相同大小的台阶。每一个楼梯由至少两个台阶组成，而每个台 阶至少由一块砖组成，下面的图片给出了当N=11和N=5的一些例子：N计算并输出能由N块砖组成的楼梯的个数Q。你的任务是根据给出的输入数字 N(5 W N W 500)输出数字Q样例输入212样例输出995645335var i,j,m,n,q:longint;f:array1.225,0.225 of longint;beginfi

16、llchar(f,sizeof(f),0);f3,1:=1;f4,1:=1;readln(n);for i: = 1 to n do fi,i:=1;for i:=5 to n dofor j:=1 to (i+1) div 2-1 dofor m:=j+1 to i-j dofi,j:=fi,j+fi-j,m;q:=0;for i: = 1 to (n+1) div 2-1 doq:=q+fn,i;writeln(q);end.金银岛在金银岛上，人们使用的货币的值都为完全平方数，例如1,4,9289.对于要支付十元的话就有下列四种办法。1：十个一元的钱。2： 一个四元的，六个一元的。3：二个

17、四元的，二个一元的。4： 一个九元的，一个一元的。你的任务在于对于给定的钱数(设其值少于300)，给出有多少种支付的方法.Sample Input210300Sample Output1427program jinyindao;var y,x,number,i,n,money:integer;moneyrange:array1.20 of longint;f:array0.20,0.300 of longint;a:array1.100 of integer;procedure getdata;beginassign(input,data/a/jinyindao.in);reset(input

18、);for y:=1 to 100 dobeginreadln(ay);if ay=0 then break;end;close(input);end;procedure chuli;var m:integer;beginfor m:=1 to 17 domoneyrangem:=m*m;n:=trunc(sqrt(money);end;begingetdata;for y:=1 to 100 dobeginif ay=0 then breakelsebeginmoney:=ay;chuli;for i:=1 to n dofi,0： = 1；for x:=1 to money dof0,x:

19、=0;f0,0：=1；for i:=1 to n dofor number:=1 to money dobeginif number=moneyrangei thenfi,number:=fi-1,number+fi,number-moneyrangeielse fi,number:=fi-1,number;end;writeln(fn,money);end;end;end.网上的一种方法先把i种货币按照面值排序，f(i,n)表示前i种货币支付n的方法。，决策是用 不要第 i 种货币。有方程：f(i,n)=f(i-1,n)+f(i,n-wi)f(0,0): = 1;vara : array0.

20、300of longint;i,j,k : integer;begina0: = 1;for i:=1 to 17 dobegink:=sqr(i);for j:=0 to 300-k doinc(aj+k,aj);end;repeat readln(k);if k=0 thenbreak;writeln(ak);until k=0;end.stepi,j:=stepi-1,j-vi or stepi-1,j;加分二叉树【问题描述】设一个n个节点的二叉树tree的中序遍历为(l,2,3,n),其中数字 1,2,3,n为节点编号。每个节点都有一个分数(均为正整数)，记第i个节点 的分数为di，t

21、ree及它的每个子树都有一个加分，任一棵子树subtree (也包 含tree本身)的加分计算方法如下：subtree的左子树的加分X subtree的右子树的加分+ subtree的根的分数若某个子树为空，规定其加分为1,叶子的加分就是叶节点本身的分数。不 考虑它的空子树。试求一棵符合中序遍历为(1,2,3,n)且加分最高的二叉树tree。要求 输出；tree的最高加分tree的前序遍历分析很显然，本题适合用动态规划来解。如果用数组valuei,j表示从节点 i到节点j所组成的二叉树的最大加分，则动态方程可以表示如下：valuei,j=maxvaluei,i+valuei+1,j,value

22、i+1,i+1+valuei,i*valu ei+2,j,valuei+2,i+2+valuei,i+1*valuei+3,j,valuej-1,j-1+valuei,j- 2*valuej,j, valuej,j+valuei,j-1题目还要求输出最大加分树的前序遍历序列，因此必须在计算过程中记下从节点 i到节点j所组成的最大加分二叉树的根节点，用数组rooti,j表示Ural 1018 二*苹果树题目有一棵苹果树，如果树枝有分叉，一定是分2叉(就是说没有只有1个儿子的结 点)这棵树共有N个结点(叶子点或者树枝分叉点)，编号为1-N，树根编号一定是1。 我们用一根树枝两端连接的结点的编号来描

23、述一根树枝的位置。下面是一颗有4 个树枝的树25 /34 /1现在这颗树枝条太多了，需要剪枝。但是一些树枝上长有苹果。给定需要保留的树枝数量，求出最多能留住多少苹果。输入格式第 1 行 2 个数，N 和 Q(1=Q= N,1N=100)。N表示树的结点数，Q表示要保留的树枝数量。接下来N-1行描述树枝的信息。每行3个整数，前两个是它连接的结点的编号。第3个数是这根树枝上苹果的数 量。每根树枝上的苹果不超过30000个。输出格式一个数，最多能留住的苹果的数量。解析：因为题目一给出就是二叉的，所以很容易就可以写出方程：a(I,j):二max(a(i.left,k)+a(i.right,j-k),0

24、=kj then j:=k;end;treedp:二j;End;问题描述在大学里每个学生，为了达到一定的学分，必须从很多课程里选择一些课程来学 习，在课程里有些课程必须在某些课程之前学习，如高等数学总是在其它课程之 前学习。现在有N门功课，每门课有个学分，每门课有一门或没有直接先修课(若 课程a是课程b的先修课即只有学完了课程a，才能学习课程b)。一个学生要从 这些课程里选择M门课程学习，问他能获得的最大学分是多少？输入：第一行有两个整数N,M用空格隔开。(1=N=200,1=M=150)接下来的N行，第I+1行包含两个整数ki和si, ki表示第I门课的直接先修课， si表示第I门课的学分。

25、若ki=0表示没有直接先修课(1=ki=N, 1=si=0 then exit;treedp(ax.r,y);只有右子树的情况j:=bax.r,y;for k:=1 to y do(左右子树都有的情况begintreedp(ax.l,k-1);treedp(ax.r,y-k);i:=bax.l,k-1+bax.r,y-k+ax.k;if ij then j:=i;end;bx,y:=j;end;beginreadln(s);assign(input,s);reset(input);readln(n,m);fillchar(f,sizeof(f),0);for i:=0 to n dobegin

26、 ai.l:=-1;ai.r:=-1;ai.k:=-1;end;(build treefor i:=1 to n dobeginreadln(k,l);ai.k:=l;if fk=0 then ak.l:=ielse afk.r:=i;fk:=i;end;(bianjiefor i:=-1 to n dofor j:=-1 to m doif (i=-1) or (j=0) then bi,j:=0 else bi,j:=-1;(tree dptreedp(a0.l,m);(outputwriteln(ba0.l,m);end.Tju1053技能树Problem 玩过Diablo的人对技能树一

27、定是很熟悉的。一颗技能树的每个结点都是一项技 能，要学会这项技能则需要耗费一定的技能点数。只有学会了某一项技能以后，才能继续学习它的后继技能。每项技能又有着不同 的级别，级别越高效果越好，而技能的升级也是需要耗费技能点数的。有个玩家积攒了一定的技能点数，他想尽可能地利用这些技能点数来达到最好的 效果。因此他给所有的级别都打上了分，他认为效果越好的分数也越高。现在他要你帮忙寻找一个分配技能点数的方案，使得分 数总和最高。Input该题有多组测试数据。每组测试数据第一行是一个整数n（1=n=20），表示所有不同技能的总数。接下来依次给出n个不同技能的详细情况。每个技能描述包括5行。第一行是该技能的

28、名称。第2行是该技能在技能树中父技能的名称，名称为None则表示该技能不需要任 何的先修技能便能学习。第3行是一个整数L（1=L=20），表示这项技能所能拥有的最高级别。第4行共有L个整数，其中第I个整数表示从地I-1级升到第I级所需要的技能 点数（0级表示没有学习过）。第5行包括L个整数，其中第I个整数表示从第I-1级升级到第I级的效果评分， 分数不超过20。在技能描述之后，共有两行，第1行是一个整数P，表示目前所拥有的技能点数。 接下来1行是N个整数，依次表示角色当前习得的技能级别，0表示还未学习。 这里不会出现非法情况。Output每组测试数据只需输出最佳分配方案所得的分数总和。解析：这

29、题是选课的加强版，但并难不倒我们还是把一棵树转换为二叉树，完后从子节点到根节点作一次dp，最后得到最优 解由于和上题很相像就不写方程了。源代码程序：program bluewater;type tree=records,sf:string;l,r,m:longint;c:array1.20 of longint;d:array1.20 of longint;end;vari,j,k,l,m,n:longint;a:array0.20 of tree;b:array0.20 of longint;learn:array0.20 of longint;f:array0.20,0.8000 of l

30、ongint;function treedp(x,y:longint):longint;var i,j,k,l,max,o,p,q:longint;beginif fx,y-1 then begin treedp:=fx,y;exit;end;max:二treedp(ax.r,y);learn0if learnx0 thenbeginfor k:=0 to y dobegini:二treedp(ax.l,k)+treedp(ax.r,y-k);if imax then max:=i;end;end;(learn=0l:=0;p:=0;i:=0;for o:=1 to ax.m dobegini

31、f olearnx thenbegin l:=l+ax.co;p:=p+ax.do;end;for k:=0 to y-l dobegini:二treedp(ax.l,k)+treedp(ax.r,y-l-k)+p;if imax then max:=i;end;end;fx,y:二max;treedp:二max;end;function find(x:string):longint;var i,j:longint;beginfor i:=0 to n doif ai.s=x then break;find:=i;end;beginwhile not(eof(input) dobegin(in

32、putreadln(n);fillchar(a,sizeof(a),0);fillchar(b,sizeof(b),0);a0.s:=None;for i:=1 to n dowith ai dobeginreadln(s);readln(sf);readln(m);for j:=1 to m do read(cj);readln;for j:=1 to m do read(dj);readln;end;readln(m);if m8000 then m:=8000;for i:=1 to n do read(learni);readln;(build binary treefor i:=1

33、to n dobegink:=find(ai.sf);if bk=0 thenbegin bk:=i;ak.l:=i;endelse begin abk.r:=i;bk:=i;end;end;(bian jiefor i:=0 to 20 dofor j:=0 to 8000 dofi,j:=-1;for i:=0 to 8000 do f0,i:=0;(mainwriteln(treedp(a0.l,m);end;end.战略游戏ProblemBob喜欢玩电脑游戏，特别是战略游戏。但是他经常无法找到快速玩过游戏的办 法。现在他有个问题。他要建立一个古城堡，城堡中的路形成一棵树。他要在这棵树的

34、结点上放置最少 数目的士兵，使得这些士兵能了望到所有的路。注意，某个士兵在一个结点上时，与该结点相连的所有边将都可以被了望到。请你编一程序，给定一树，帮Bob计算出他需要放置最少的士兵.Input第一行为一整数M，表示有M组测试数据每组测试数据表示一棵树，描述如下：第一行N，表示树中结点的数目。第二行至第N+1行，每行描述每个结点信息，依次为：该结点标号i，k（后面有 k条边与结点I相连）。接下来k个数，分别是每条边的另一个结点标号r1，r2, .，rk。对于一个n（0n=1500）个结点的树，结点标号在0到n-1之间，在输入数据中 每条边只出现一次。Output输出文件仅包含一个数，为所求的

35、最少的士兵数目。例如，对于如下图所示的树：答案为1（只要一个士兵在结点1上）。Sample Input240 1 1 TOC o 1-5 h z 2 2 30053 1 4 21 000 00Sample Output12Sourcesgoi 分析：这题有2种做法，一种是比较简单但不是很严密的贪心，如果测试数据比 较刁钻的话就不可能ac，而这题是一道比较典型的树型动态规划的题目，这题 不但要考虑子节点对他的根节点的影响，而且每放一个士兵，士兵所在位置既影 响他的子节点也影响了他的根节点。不过状态还是很容易来表示的，动规实现也 不是很难，不过这在这些例题中也有了些“创新”了。而且这题不是一个对二

36、叉 树的dp，而是对一颗普通树的dp，所以更具代表性。源程序代码：program bluewater;constmaxn=1500;vari,j,k,l:longint;m,n,p,q:longint;a:array0.maxn,0.maxn of boolean;b:array0.maxn of longint;c:array0.maxn of boolean;function leaf(x:longint):boolean;var i,j:longint;t:boolean;begint:=true;for i:=0 to n-1 doif ax,i then begin t:=false

37、;break;end;leaf:=t;end;function treedp(x:longint):longint;var i,j,k,l:longint;beginj:=0;addk:=0;leafl:=0;(not put not leaffor i:=0 to n-1 doif (ax,i) and (xi) thenif leaf(i) then inc(k) elsebeginj:=j+treedp(i);if not(ci) then inc(l);end;puanduanif (k0) or (l0) then begin cx:=true;treedp:=j+1;exit;en

38、d;if (j0) and (l=0) then begin treedp:二j;exit;end;end;begininputreadln(m);for p:=1 to m dobeginfillchar(b,sizeof(b),0);fillchar(a,sizeof(a),false);fillchar(c,sizeof(c),false);readln(n);for i:=1 to n dobeginread(k,l);for j:=1 to l dobeginread(q);ak,q:二true;bq:=1;end;readln;end;mainfor i:=0 to n-1 doi

39、f bi=0 then break;fillchar(b,sizeof(b),0);if leaf(i) then writeln(l) else writeln(treedp(i);end;end.(最长上升子序列)描述：给一队排列整齐的数列ai,找到数列ai中最长上升子序列。输入：第一行是数列的元素个数匕第二行是N个整数，范围从0到10,000。 (1=N=1000)输出：包括一个整数，表示最长上升子序列的长度。Sample Input71 7 3 5 9 4 8Sample Output4题解：经典的Dp问题，求最长上升子序列。我用的是O(N”2)的方法。状态转移方程是di=maxdk

40、+ 1)(ki且akaj)and(dimax then max:=di;writeln(max);end;begininit;dp;findmax;end.方法二pascal动态规划里的最长上升子序列vara,fDP 记录,p后面的:array1.1000of longint; i,j,k,n:longint;beginreadln(n);for i:=1 to n dobeginread(ai);fi:=1;(预处理end;for i:=n-1 downto 1 dofor j:=n downto i+1 doif (aiaj)and(fijthen beginj:=fi;k:=i;end;

41、writeln(j);while k0 dobeginwrite(k,);k:=pk;end;end.这是n2的算法，大牛会写nlog(n)的算法，就是用堆来优化方法三Program upzxl;Var n,I,j,maxi,maxlen:longint;A,f:array1.1000 of longint;F1,f2:text;BeginAssign(f1, input.txt)；reset(f1);Assign(f2, output.txt)；rewrite(f2);Readln(f1,n);For i:=1 to n do read(f2,ai);F1: = 1;For i:=2 to

42、n dobeginmaxi:=0;for j:=1 to i-1 do if aiaj then if maxifj then maxi:=fj;fi:二maxi+1;end;maxlen:=0;for i:=1 to n do if maxlenfi then maxlen:=fi;writeln(f2,maxlen);close(f1);close(f2);end.巡回演出题目描述：Flute市的Phlharmoniker乐团2000年准备到Harp市做一次大型演出，本着普及古典音乐 的目的，乐团指挥准备在到达Harp市之前先在周围一些小城市作一段时间的巡回演出，此 后的几天里，音乐家们将

43、每天搭乘一个航班从一个城市飞到另一个城市,最后才到达目的地Harp 市(乐团可多次在同一城市演出).由于航线的费用和班次每天都在变,城市和城市之间都有一份循环的航班表,每一时间，每一 方向，航班表循环的周期都可能不同.现要求寻找一张花费费用最小的演出表.输入：输入文件包括若干个场景.每个场景的描述由一对整数n(2=n=10)和k(1=k=1000)开始, 音乐家们要在这n个城市作巡回演出，城市用1.n标号，其中1是起点Flute市,n是终点Harp 市，接下来有n*(n-1)份航班表，一份航班表一行，描述每对城市之间的航线和价格,第一组n-1份 航班表对应从城市1到其他城市(2,3,.n)的航

44、班，接下的n-1行是从城市2到其他城市 (1,3,4.n)的航班，如此下去.每份航班又一个整数d(1=d=30)开始，表示航班表循环的周期，接下来的d个非负整数表示 1,2.d天对应的两个城市的航班的价格，价格为零表示那天两个城市之间没有航班.例如3 75 0 80表示第一天机票价格是75KOI,第二天没有航班，第三天的机票是80KOI,然后循环:第四天又 是75KOI,第五天没有航班，如此循环.输入文件由n=k=0的场景结束.输出：对每个场景如果乐团可能从城市1出发，每天都要飞往另一个城市,最后(经过k天)抵达城市n,则输出这k个航班价格之和的最小值.如果不可能存在这样的巡回演出路线，输出0

45、.样例输入：3 6130 15075 0 807 120 110 0 100 110 120 060 70 60 503 0 135 1402 70 802 32 0 701 800 0样例输出：4600初看这道题，很容易便可以想到动态规划，因为第x天在第y个地方的最优值只与第x-1天有 关，符合动态规划的无后效性原则，即只与上一个状态相关联，而某一天x航班价格不难求出 S=C(x-1) mod m +1.我们用天数和地点来规划用一个数组A1.1000,1.10来存储,Ai,j表 示第i天到达第j个城市的最优值,Ci,j,l表示i城市与j城市间第l天航班价格，则 Ai,j=MinAi-1,l+

46、Cl,j,i (l=1.n 且 Cl,j,i0),动态规划方程一出，尽可以放怀大笑 了.示范程序:program p erf or m_hh;varf_, f out ： teKt;p, L i, .Sn,k： integer;a： array 1. . 1000 1. . 10 of integer; 动态规划数组c： array 1. . 10,1. . 10 of record 航EE价格数组num：integer;t:array 1.30 of integer;end;e：array 1. . 1000 of integer;procedure work;begin人工赋第一天各城市最

47、优值for i：=l to n dobeginif c lj i. t 1 0then alj i ： = c 13 i. t 1;end;for i：=2 to k dobeginIfor j：=1 to n dobeginfor 1：=1 to n dobeginif (jOl)and (c 1, j. t (il) mod c 1, j. nnni+1 0) 判断存在航班and (ai_, j=0)or (ai-lj l+c 1., j. t (i_l) mod c 1., j. num+1 ai_, j) 判断比当前解忧then ai., j ：=31-1, l+c 1, j. t (

48、i-l) mod c 1., j. num+1; 赋值end;end;end;ep ：=ak, n ; 第口个场景的最优值end;procedure readfile;读文件beginassign(f_,J PERFORM. DAT5 ) ; reset (f);assign(tout,3 PERFORM.OUT ); rewrite (tout)readln(f _,k) ; p：=0;while (n0) anddobeginP:=P+1；fillchar (c_, sizeof (c) 0);fillchar(a, sizeof(a)0);for i：=l to n dobeginfor

49、 j：=1 to i-l dobeginread(f_, c i., j. num);for 1： = 1 to c i., j . num doread(f, c i, j. t 1);end;for j：=i+l to n dobeginread(f_, c i., j. num);for 1： = 1 to c i., j . num doread(f, c i., j. t 1);end;end;work;xeadln (f., k);end;输出各个场景的解for i：=l to p-l dowiitelnff out, e i) write(fout, ep);I close (f

50、);close(fout);end;beginreadfile;end.动态规划作业最长公共子序列问题LCS问题描述一个给定序列的子序列是在该序列中删去若干元素后得到的序列。确切地说，若 给定序列X=x1, x2,，xm，则另一序列Z=z1, z2,，zk是X的子序列是 指存在一个严格递增的下标序列i1, i2,., ik，使得对于所有j=1,2,.,k 有例如，序列Z=B,C,D,B是序列X=A,B,C,B,D,A,B的子序列，相应的递增下标 序列为 2,3,5,7。给定两个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是 序列X和Y的公共子序列。例如，若X=A, B, C,

51、B, D, A, B和Y=B, D, C, A, B, A，则序列B, C, A是X和Y的一个公共子序列，序列B, C, B, A也是X 和Y的一个公共子序列。而且，后者是X和Y的一个最长公共子序列，因为X 和Y没有长度大于4的公共子序列。最长公共子序列(LCS)问题：给定两个序列X=x1, x2,，xm和Y=y1, y2,， yn，要求找出X和Y的一个最长公共子序列。输入文件有两行，每行为一个有大写字母构成的长度不超过200的字符串，表示序列 X和Y。输出输出文件第一行为一个非负整数，表示所求得的最长公共子序列长度，若不存在公共子序列，则输出文件仅有一行输出一个整数0,否则在输出文件的第二行输 出所求得的最长公共子序列(也用一个大写字母组成的字符串表示)，若符合条 件的最长公共子序列不止一个，只需要输出其中任意的一个。样例输入：LCS.