动态规划2014

1、动态规划2014附中讲义类型n资源分配（背包）n线性n区间n树形n动规+贪心n动规+穷举n其他一 资源问题 1 机器分配问题 n总公司拥有高效生产设备M台，准备分给下属的N个公司。各分公司若获得这些设备，可以为国家提供一定的盈利。问：如何分配这M台设备才能使国家得到的盈利最大？求出最大盈利值。其中M=15，N=10。分配原则：每个公司有权获得任意数目的设备，但总台数不得超过总设备数M。n 数据文件格式为：第一行保存两个数，第一个数是设备台数M，第二个数是分公司数N。接下来是一个M*N的矩阵，表明了第I个公司分配J台机器的盈利。 n用机器数来做状态，数组FI，J表示前I个公司分配J台机器的最大盈

2、利。则状态转移方程为:nFI,j:=max(fi-1,k+wi,j-k) 2 01背包问题 n一个旅行者有一个最多能用M公斤的背包，现在有N件物品，它们的重量是Wi,它们的价值为Pi。若每种物品只有一件求旅行者能获得最大总价值。输入格式：M,NW1,P1W2,P2.输出格式： X ncij数组保存了1,2,3号物品依次选择后的最大价值.nf(n,m)=maxf(n-1,m), f(n-1,m-wn)+Pn3 系统可靠性(完全背包) n有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费用是c，价值是w。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大

3、。 n Fi,j:=maxfi-1,j-ci*k+k*wi nK=0j系统可靠性 n一个系统由若干部件串联而成，只要有一个部件故障，系统就不能正常运行，为提高系统的可靠性，每一部件都装有备用件，一旦原部件故障，备用件就自动进入系统。显然备用件越多，系统可靠性越高，但费用也越大，那么在一定总费用限制下，系统的最高可靠性等于多少？n给定一些系统备用件的单价Ck，以及当用Mk个此备用件时部件的正常工作概率PkMk，总费用上限C。n求系统可能的最高可靠性。n输入文件格式：n第一行： n C n第二行： C1 P10 P11 P1X1 (0=X1=C/Ck) n n第 n 行： Cn Pn0 Pn1 P

4、nXn （0=Xn=C/Cn ）n输入： 2 20 3 0.6 0.65 0.7 0.75 0.8 0.85 0.9 5 0.7 0.75 0.8 0.8 0.9 0.95 n输出： 0.6375 nFI,money:将将money的资金用到前的资金用到前I项备用件中可项备用件中可得的最大可靠性，得的最大可靠性， nFI,money=maxFI-1,moneyk*CI +PI, k (0=I=n, 0=K= money div Cost(I) ) nF0,0 =0 nFn,C?4 金明的预算方案 n金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间金明自己专用的很宽敞的房间。更让他高兴的

5、是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N元钱就行”。今天一早，金明就开始做预算了，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的，下表就是一些主件与附件的例子： 主件 附件 电脑 打印机，扫描仪 书柜 图书 书桌 台灯，文具 工作椅 无n如果要买归类为附件的物品，必须先买该附件所属的主件。每个主件可以有0个、1个或2个附件。附件不再有从属于自己的附件。金明想买的东西很多， 肯定会超过妈妈限定的N元。于是，他把每件物品规定了一个重要度，分为5等：用整数15表示，第5等最重要。他还从因特网上查到了每件物品的价格（都是 10元的整数倍）。他希望在不

6、超过N元（可以等于N元）的前提下，使每件物品的价格与重要度的乘积的总和最大。n设第j件物品的价格为vj，重要度为wj，共选中了k件物品，编号依次为j1，j2，jk，则所求的总和为：nvj1*wj1+vj2*wj2+ +vjk*wjk。（其中*为乘号） n请你帮助金明设计一个满足要求的购物单。n第1行，N m (N32000表示总钱数，m60为希望购买物品的个数。) 从第2行到第m+1行，第j行给出了编号为j-1的物品的基本数据，每行有3个非负整数 v p q (v0，所属主件的编号）n输出只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（200000）。n【输入样例】 10

7、00 5 800 2 0 400 5 1 300 5 1 400 3 0 500 2 0 【输出样例】 2200 n“每个主件可以有个，个或个附件”。降低复杂度。n对于一套物品（包含主件，所有的附件），我们称为一个类，对一个类的物品的购买方法，有以下种：.一个都不买.主件.主件附件.主件附件.主件附件附件n把物品的类作为dp的状态。fi,j=maxfi-1,j;fi-1,j-vi,0+vi,0*wi,0;fi-1,j-vi,0-vi,1+vi,0*wi,0+vi,1*wi,1;fi-1,j-vi,0-vi,2+vi,0*wi,0+vi,2*wi,2;fi-1,j-vi,0-vi,1-vi,2+

8、vi,0*wi,0+vi,1*wi,1+vi,2*wi,2;n时间复杂度O(n2)，空间复杂度O(n2)，n“每件物品都是10元的整数倍” 5 化工场装箱员 n118号工厂是世界唯一秘密提炼锎的化工厂，由于提炼锎的难度非常高，技术不是十分完善，所以工厂生产的锎成品可能会有3种不同的纯 度，A：100%，B：1%，C：0.01%，为了出售方便，必须把不同纯度的成品分开装箱，装箱员grant第1次顺序从流水线上取10个成品（如果一 共不足10个，则全部取出），以后每一次把手中某种纯度的成品放进相应的箱子，然后再从流水线上顺序取一些成品，使手中保持10个成品（如果把剩下的全部 取出不足10个，则全部

9、取出），如果所有的成品都装进了箱子，那么grant的任务就完成了。n由于装箱是件非常累的事情，grant希望他能够以最少的装箱次数来完成他的任务，现在他请你编个程序帮助他。nworker.in11ABCABCABCABnworker.out3nfst,a,b,c 到到st这个位置时，剩余这个位置时，剩余A（a个），个），B（b个），个），C（c个），个）， nfst,a1,b1,c1:=min(fst,a1,b1,c1,dfs(st,0,b1,c1)+1，dfs(st,a1,0,c1)+1，dfs(st,a1,b1,0)+1); 6 背包问题n你刚刚继承了流行的“破锣摇滚”乐队录制的尚未发表的

10、N(1 = N = 20)首歌的版权。你打算从中精选一些歌曲，发行M(1 = M = 20)张CD。每一张CD最多可以容纳T(1 = T = 20)分钟的音乐，一首歌不能分装在两张CD中。 n不巧你是一位古典音乐迷，不懂如何判定这些歌的艺术价值。于是你决定根据以下标准进行选择： n歌曲必须按照创作的时间顺序在CD盘上出现。选中的歌曲数目尽可能地多。n第一行： 三个整数：N, T, M. 第二行： N个整数，分别表示每首歌的长度，按创作时间顺序排列。n一个整数，表示可以装进M张CD盘的乐曲的最大数目。 n4 5 24 3 4 236 背包问题 n多个背包，不可以重复放物品，但放物品的顺序有限制。

11、nFI,j,k表示决策到第i个歌曲、第j个CD，用了k分钟的空间，能刻的最多歌曲数。nfI,j,k:=max(fI-1,j,k,fI-1,j,k-Li+1,fi-1,j-1,t-Li)7 装箱问题(判定性01背包) n有个容量为有个容量为c 的箱子和的箱子和n 个待装载入箱子中的物品。个待装载入箱子中的物品。物品物品i 需占用需占用si个单元（个单元（0sic）。成功装载是）。成功装载是指剩余空间最大。指剩余空间最大。nfj:=(fj or fj-v)n某运输公司要把包裹装入卡车中，每个包裹都有某运输公司要把包裹装入卡车中，每个包裹都有一定的重量，且每辆卡车也有其载重限制（假设一定的重量，且每

12、辆卡车也有其载重限制（假设每辆卡车的载重都一样）。在卡车装载问题中，每辆卡车的载重都一样）。在卡车装载问题中，希望用最少的卡车来装载包裹。希望用最少的卡车来装载包裹。8 背包问题(+-1背包问题+回溯)n给出一列数,可以对这列数进行一种操作con(a1,a2.an,c)表示把a1,a2.an这列数中的ac,a(c+1)取出,再把ac-a(c+1)放回原处,显然,每操作一次序列长度减1.求一个长度为n-1的操作顺序,使得第一个操作以初始序列为操作对象,从第二个操作开始每个操作都以上一个操作得到的序列为操作对象,并使得最后剩下的数为t.可以假定对于输入至少有一个可行的操作序列.n1=N=100,n

13、-10000=T=10000n1=ai=1008 背包问题(+-1背包问题+回溯)Subtract.inSubtract.out4 510 2 5 21 2 15 412 10 4 3 52 3 2 18 背包问题(+-1背包问题+回溯) ndij表示前i个数获得j结果是否可能ndij=di-1j-ai-1|di-1j+ai-1动态规划解决问题的基本特征1. 动态规划一般解决最值（最优，最大，最小，最长）问题；2. 动态规划解决的问题一般是离散的，可以划分阶段的；3. 动态规划解决的问题必须包含最优子结构，即可以由（n1）的最优推导出n的最优n1. 刻画最优解的结构特性. （一维，二维，三维数

14、组） 2. 递归的定义最优解. （状态转移方程） 3. 以自底向上的方法来计算最优解. 4. 从计算得到的解来构造一个最优解.动态规划的4个步骤排队买票问题n 一场演唱会即将举行。现有n个歌迷排队买票，一个人买一张，而售票处规定，一个人每次最多只能买两张票。假设第i位歌迷买一张票需要时间Ti（1in），队伍中相邻的两位歌迷（第j个人和第j+1个人）也可以由其中一个人买两张票，而另一位就可以不用排队了，则这两位歌迷买两张票的时间变为Rj，假如RjTj+Tj+1，这样做就可以缩短后面歌迷等待的时间，加快整个售票的进程。现给出n, Tj和Rj，求使每个人都买到票的最短时间和方法。如果前如果前i个人买

15、票的最优买票方式一确定，个人买票的最优买票方式一确定，比如第比如第i个人买一张票，则前个人买一张票，则前i-1个人的买个人的买票方式也一定是最优的。即问题的最优票方式也一定是最优的。即问题的最优解包含子问题的最优解。解包含子问题的最优解。12345iin-1nn-2步骤步骤1：用用F（i）表示前）表示前i个人买票的最优方个人买票的最优方式，即所需最短时间；式，即所需最短时间； （1）第i个人的票自己买 （2）第i个人的票由第i-1个人买步骤步骤2：状态转移方程：状态转移方程：min步骤步骤3：以自底向上的方法来计算最优解以自底向上的方法来计算最优解1100 1min 1, 2iiif iTif

16、 iT f iR-=-+-+ 二、线性动态规划n经典n最长不下降序列n数字三角形1.拦截导弹n某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导

17、弹。有可能不能拦截所有的导弹。n输入描述输入描述n导弹依次飞来的高度（雷达给出的高度数据是不大于导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数）的正整数）n输出描述输出描述n计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。多少套这种导弹拦截系统。n样例输入样例输入n389 207 155 300 299 170 158 65 n给定给定N个数个数q求最长的不上升子序列长度求最长的不上升子序列长度q求最少有多少个不上升序列能覆盖所有的数，求最少有多少个不上升序列能覆盖所有的数，即求最

18、少覆盖序列。即求最少覆盖序列。nN=10000.分析n设设f(i)表示前表示前i个数的最长不上升序列的长度。个数的最长不上升序列的长度。则则,f(i)=maxf(j)+1,其中其中j=ai这里这里0ji=n。显然时间复杂度为显然时间复杂度为O(n2)。n上述式子的含义：找到上述式子的含义：找到i之前的某之前的某j，这个数不比，这个数不比第第i个数小个数小,对于所有的对于所有的j取取f(j)的最大值。的最大值。 优化n分析样例分析样例 n这里找这里找j,是在是在1i之间进行寻找，那么我们能否快速查找到我们所要更之间进行寻找，那么我们能否快速查找到我们所要更改的改的j呢呢?n要能更改需要两个条件：

19、要能更改需要两个条件：qj=aiqf(j)尽可能大尽可能大 n以上两个条件提示我们后面的值一定要小于等于前面的值。因此我们以上两个条件提示我们后面的值一定要小于等于前面的值。因此我们试着构建一个下降的序列。在这个下降的序列中查找可以更改的试着构建一个下降的序列。在这个下降的序列中查找可以更改的f值值,使得序列的值尽可能大。使得序列的值尽可能大。i1234567838920715530029917015865f12323456n具体过程：i1234567838920715530029917015865第第1次次389第第2次次389207第第3次次389207155第第4次次389300155（

20、由于（由于207300389,因此更新）因此更新）第第5次次389300299（由于（由于155299300,因此更新）因此更新）第第6次次389300299170第第7次次389300299170158第第8次次38930029917015865思考？n对于该序列，为什么要保留较大的值呢？对于该序列，为什么要保留较大的值呢？nf(i)=maxf(j)+1,其中其中j=ai该式子表示找前面的一个最大该式子表示找前面的一个最大f的符合条件的的符合条件的j，因此只要保存符合条，因此只要保存符合条件的最大的件的最大的j就可以了。就可以了。n在在f值相同的情况下，保留较大的数显然更好。因为后面的数若能

21、跟较值相同的情况下，保留较大的数显然更好。因为后面的数若能跟较小的数构成下降序列也一定能能较大的数构成下降序列，反之则不一小的数构成下降序列也一定能能较大的数构成下降序列，反之则不一定。例如定。例如207与与300的的f=2,但但207不能与不能与299构成下降序列，而构成下降序列，而300则可以。则可以。因为生成的序列为有序序列，因此我们可以采用二分查找的方法很快因为生成的序列为有序序列，因此我们可以采用二分查找的方法很快查找到更新的值，时间复杂度为查找到更新的值，时间复杂度为O(nn)求导弹的最小覆盖n第二问很容易想到贪心法：那就是采取多次求最长不上升序列的办法，然后得出总次数。n上述贪心

22、法不正确，很容易就能举出反例。例如： “7 5 4 1 6 3 2”用多次求最长不上升序列所有为“7 5 4 3 2”、“1”、“6”共3套系统；但其实只要2套，分别为： “7 5 4 1”与“6 3 2”。n那么，正确的做法又是什么呢？ 解决解决n最少多少套系统最少多少套系统 = 最长导弹高度上升序列长度。最长导弹高度上升序列长度。n知道了怎样求最长不上升算法，同样也就知道了知道了怎样求最长不上升算法，同样也就知道了怎样求最长上升序列。怎样求最长上升序列。n时间复杂度时间复杂度O(nn)。输入一个长度为的整数序列（输入一个长度为的整数序列（A1,A2,An），从中找出），从中找出一段长度不超

23、过一段长度不超过m的连续的子序列，使得这个序列的和最大。的连续的子序列，使得这个序列的和最大。例如：序列例如：序列 1， -3， 5， 1， -2， 3当当M=2或或3时时,S=5+1=6当当M=4时时,S=5+1-2+3=7数据范围数据范围: 50%的数据的数据N,M=1000 100%的数据的数据N,M=200002、最大子序和最大子序和 输入一个长度为的整数序列（A1,A2,An），从中找出一段连续的子序列，使得这个序列的和最大。 和原问题相比没有M这个序列长度的限制！一个简化的问题序列的最大连续和 设设 F(i)表示以第表示以第i个数结尾的最大连续和个数结尾的最大连续和 以第以第i个数

24、结尾的最大连续和序列，可能存在两种选择：个数结尾的最大连续和序列，可能存在两种选择： 情形一：只包含情形一：只包含Ai 情形二：包含情形二：包含Ai和以和以Ai-1结尾的最大连续和序列结尾的最大连续和序列状态转移方程如下：状态转移方程如下： F(i)=maxAi , F(i-1)+Ai边界：边界：F(1)=A1，Ans=maxF(i)|1=i=n该算法的时间复杂度为该算法的时间复杂度为O(n)分析设 F(i)为以Ai结尾长度不超过M的最大子序和 ikijjmkAiF11|max)(? 对于每个F(i)，从1到m枚举k的值，完成Aj的累加和取最大值。该算法的时间复杂度为O(n3)算法一 枚举ik

25、ijjmkAiF1.1|max)(i1jjA) i (S令.1| )(min)(.1| )()(maxmkkiSiSmkkiSiS简化方程 用一个二叉堆来维护用一个二叉堆来维护S(i-k)，每次求，每次求F(i)之前的操作如之前的操作如下：下：.1| )(min)()(mkkiSiSiF求求F(i-1)时，求时，求minS(i-m-1), ,S(i-2)求求F(i)时，时， 求求minS(i-m),S(i-1)在堆中删除元素在堆中删除元素S(i-m-1)，插入元素，插入元素S(i-1).复杂度复杂度O(2log2n)从堆中取出当前最小值从堆中取出当前最小值.复杂度复杂度O(1) 所以计算的总复

26、杂度为所以计算的总复杂度为O(nlog2n)算法二 堆优化 在算法二中，考虑用队列来维护决策值在算法二中，考虑用队列来维护决策值S(i-k)。每次只需要在队首删掉每次只需要在队首删掉S(i-m-1)，在队尾添加，在队尾添加S(i-1) 。但是取最小值操作还是需要。但是取最小值操作还是需要O(n)时间复杂度时间复杂度的扫描。的扫描。 考察在添加考察在添加S(i-1)的时候，设现在队尾的元素是的时候，设现在队尾的元素是S(k)，由于，由于ki-1，所以，所以S(k)必然比必然比S(i-1)先出队。先出队。若此时若此时S(i-1)=S(k)，则，则S(k)这个决策永远不会在以这个决策永远不会在以后用

27、到，可以将后用到，可以将S(k)从队尾删除掉（此时队列的尾从队尾删除掉（此时队列的尾部形成了一个类似栈的结构）部形成了一个类似栈的结构）算法三 队列优化 同理，若队列中两个元素同理，若队列中两个元素S(i)和和S(j)，若若i=S(j)，则我们可以删掉，则我们可以删掉S(i)（因为（因为S(i)永远不会被用到）。此时的队永远不会被用到）。此时的队列中的元素构成了一个单调递增的序列，列中的元素构成了一个单调递增的序列，即：即：S1S2S3Sk队列优化用队列维护S(i-k)所需要的操作： 若当前队首元素S(x)，有x=i-m为止。 若当前队尾元素S(k)=S(i-1)，则S(k)出队；直到S(k)

28、S(i-1)为止。 在队尾插入S(i-1) 取出队列中的最小值，即队首元素。算法三对于求每个对于求每个F(i)的时候，进队和出队的元的时候，进队和出队的元素不止一个。素不止一个。每一个元素每一个元素S(i)只进队一次、出队一次，只进队一次、出队一次，所以队列维护的时间复杂度是所以队列维护的时间复杂度是O(n)。而每。而每次求次求F(i)的时候取最小值操作的复杂度是的时候取最小值操作的复杂度是O(1)，所以这一步的总复杂度也是，所以这一步的总复杂度也是O(n)。 综上所述，该算法的总复杂度是综上所述，该算法的总复杂度是O(n)算法三3、理想收入问题、理想收入问题n理想收入是指在股票交易中，以理想

29、收入是指在股票交易中，以1元为本金可能获元为本金可能获得的最高收入，并且在理想收入中允许有非整数得的最高收入，并且在理想收入中允许有非整数股票买卖。股票买卖。n已知股票在第已知股票在第i天每股价格是天每股价格是Vi元，元，1iM，求，求M天后的理想收入。天后的理想收入。方法一方法一n设设Fi表示在第表示在第i天收盘时能达到的最高收入，则天收盘时能达到的最高收入，则有有Fi的递推关系式：的递推关系式：1010*/ max)0(VFiVkVjFiFikj，其中公式含义：在第公式含义：在第i天收盘时能达到的最高的收天收盘时能达到的最高的收入，是将第入，是将第j天收盘后的收入，全部用于买入天收盘后的收

30、入，全部用于买入第第k天的股票，再在第天的股票，再在第i天将所持的股票全部天将所持的股票全部卖出所得的收入。卖出所得的收入。时间复杂度是时间复杂度是O(M3)。方法二方法二n设设Pi表示前表示前i天能获得的最多股票数，则可列出天能获得的最多股票数，则可列出状态转移方程：状态转移方程：n设设Qi表示前表示前i天能达到的最大收入，则可列出状天能达到的最大收入，则可列出状态转移方程：态转移方程： / *,1max)0(iVjVjPiPiPij*/ ,1max)0(iVjVjQiQiQij时间复杂度是时间复杂度是O(M2)。方法三方法三n分析：上述公式的含义是当分析：上述公式的含义是当0=ji 时时,

31、求求Qi-1和和Qj*vi/vj的最大值的最大值 n对于对于0=ji，要求，要求Qi,实际上实际上Q1Qi-1都已经求出，因都已经求出，因此我们只要用一个变量保存此我们只要用一个变量保存Qj/Vj 的最大值即可，记为的最大值即可，记为MaxQ.n这样，公式可以写成这样，公式可以写成*/ ,1max)0(iVjVjQiQiQij*,1max)0(iVMAXQiQiQij 对每次求出的对每次求出的Qi,都更新都更新MaxQ,时间复杂度为时间复杂度为O(M)设有一个三角形的数塔，顶点结点称为根结点，每个结点有一个整数数值。从顶点出发，可以向左走，也可以向右走。 问题：当三角形数塔给出之后，找出一条从

32、第一层到达底层的路径，使路径的问题：当三角形数塔给出之后，找出一条从第一层到达底层的路径，使路径的值最大。若这样的路径存在多条，任意给出一条即可。值最大。若这样的路径存在多条，任意给出一条即可。 回顾 数字三角形二维数组二维数组 D(X,y)描述问题，描述问题，D(X,y)表示从顶层到达第表示从顶层到达第X层第层第y个位置的最小路径得分。个位置的最小路径得分。阶段分析：D(1,1)=13 到第x层的第y个位置有两种可能，要么走右分支 得到，要么走左分支得到。n D(X,y)minD(X-1,y)，D(X-1,y-1+a(X,y)n D(1,1)a(1,1) 【问题背景】栈是计算机中经典的数据结

33、构，简单的说，栈就是限制在一端进行插入删除操作的线性表。栈有两种最重要的操作，即pop（从栈顶弹出一个元素）和push（将一个元素进栈）。一个操作数序列，1n，栈A的深度大于n。现在可以进行两种操作，1.将一个数，从操作数序列的头端移到栈的头端（对应数据结构栈的push操作）2. 将一个数，从栈的头端移到输出序列的尾端（对应数据结构栈的pop操作）4、栈使用这两种操作，由一个操作数序列就可以得到一系列的输使用这两种操作，由一个操作数序列就可以得到一系列的输出序列，下图所示为由出序列，下图所示为由1 2 3生成序列生成序列2 3 1的过程。的过程。111231233222323113你的程序将对

34、给定的你的程序将对给定的n，计算并输出由操作数序列，计算并输出由操作数序列1，2，n经过操作可能得到的输出序列的总数。经过操作可能得到的输出序列的总数。【输入格式输入格式】输入文件只含一个整数输入文件只含一个整数n（1n18）【输出格式输出格式】输出文件只有一行，即可能输出序列的总数目输出文件只有一行，即可能输出序列的总数目【输入样例输入样例】3【输出样例输出样例】55、火车进站、火车进站n给定给定N辆火车辆火车q第第i辆火车的进站时间辆火车的进站时间arrive(i)q第第i辆火车的离站时间辆火车的离站时间leave(i)n车站只能容纳车站只能容纳M辆火车辆火车n求最多能接受多少辆火车？求最

35、多能接受多少辆火车？nM=3q第第1，2，3辆分别进入（辆分别进入（ 1 2 3 ）；）；q第第2辆离开，可以看出要离开时，被第辆离开，可以看出要离开时，被第1辆火车卡在前面，因此第辆火车卡在前面，因此第1辆辆火车不能进入，队列为（火车不能进入，队列为（2 3）q第第2辆离开，第辆离开，第4辆进入（辆进入（3 4）q第第3，4辆离开，队列空辆离开，队列空q第第5，6辆进入辆进入 （5 6）q第第5，6分别离开，队列空分别离开，队列空l因此答案为因此答案为5辆辆123456分析n按到达时间排序和离开时间排序，这样每一辆火车用线段按到达时间排序和离开时间排序，这样每一辆火车用线段描述，有：描述，有

36、：q排在前面的火车，其进站时间必须先于排在后排在前面的火车，其进站时间必须先于排在后面的火车；面的火车；q排在前面的火车，其出站时间必须先于排在后排在前面的火车，其出站时间必须先于排在后面的火车，否则该列火车就要先进后出，不满面的火车，否则该列火车就要先进后出，不满足队列特点。足队列特点。n这样对于任一列排序后的火车这样对于任一列排序后的火车i，只有排在其后的火车才，只有排在其后的火车才有可能在它出站之后进站。接下来的任务便是采用动态规有可能在它出站之后进站。接下来的任务便是采用动态规划方法求解了。划方法求解了。m=1时时n设设fi表示第表示第i 列火车进站时，其后的火车最多列火车进站时，其后

37、的火车最多可以进站的数量，可以进站的数量， 则有：则有：nfi =maxfj+1，（满足，（满足i比比j先进站，且先进站，且j在在i 出站之后进站）；出站之后进站）；m=2n设设fi,j表示车站停靠表示车站停靠i,j 两列火车两列火车(ij)时，其后的火车时，其后的火车（包括（包括i,j本身）最多可以进站的数量本身）最多可以进站的数量,则则:nfi,j=maxfj,k+1n条件：必须满足按条件：必须满足按i,j,k顺序进站和出站，另外还要满足顺序进站和出站，另外还要满足k在在i出站后且出站后且j 进站。进站。m=3n设设fi,j,k表示车站停靠表示车站停靠i,j,k三列火车三列火车(ijk)时

38、，其后的火车时，其后的火车（包括（包括i,j,k）最多可以进站的数量。则有，）最多可以进站的数量。则有，nfi,j,k=maxfj,k,l+1n条件：必须满足按条件：必须满足按i,j,k,l顺序进站和出站，另外还要满足顺序进站和出站，另外还要满足l在在i 出站后进站。出站后进站。6、最长公共子序列、最长公共子序列n给定的字符序列X=“x0，x1，xm-1”，序列Y=“y0，y1，yk-1”是X的子序列，存在X的一个严格递增下标序列，使得对所有的j=0，1，k-1，有xij = yj。n例如，X=“ABCBDAB”，Y=“BCDB”是X的一个子序列。n给出两个字串S1和S2，长度不超过5000.n求这两个串的最长公共子串长度。nX = (A, B, C, B, D, A, B) X = (A, B, C, B, D, A, B)nY = (B, D, C, A, B, A) Y = (B, D,