noippascal语言动态规划.ppt

第九章 动态规划,第一节 动态规划的基本模型第二节 动态规划与递推第三节 历届NOIP动态规划试题第四节 背包问题第五节 动态规划应用举例,动态规划程序设计是对解最优化问题的一种途径、一种方法，而不是一种特殊算法。不象前面所述的那些搜索或数值计算那样，具有一个标准的数学表达式和明确清晰的解题方法。动态规划程序设计往往是针对一种最优化问题，由于各种问题的性质不同，确定最优解的条件也互不相同，因而动态规划的设计方法对不同的问题，有各具特色的解题方法，而不存在一种万能的动态规划算法，可以解决各类最优化问题。因此读者在学习时，除了要对基本概念和方法正确理解外，必须具体问题具体分析处理，以丰富的想象力去建立模型，用创造性的技巧去求解。我们也可以通过对若干有代表性的问题的动态规划算法进行分析、讨论，逐渐学会并掌握这一设计方法。,第一节 动态规划的基本模型,多阶段决策过程的最优化问题,在现实生活中，有一类活动的过程，由于它的特殊性，可将过程分成若干个互相联系的阶段，在它的每一阶段都需要作出决策，从而使整个过程达到最好的活动效果。当然，各个阶段决策的选取不是任意确定的，它依赖于当前面临的状态，又影响以后的发展，当各个阶段决策确定后，就组成一个决策序列，因而也就确定了整个过程的一条活动路线，这种把一个问题看作是一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程，这种问题就称为多阶段决策问题。如下图所示：,多阶段决策过程，是指这样的一类特殊的活动过程，问题可以按时间顺序分解成若干相互联系的阶段，在每一个阶段都要做出决策，全部过程的决策是一个决策序列。要使整个活动的总体效果达到最优的问题，称为多阶段决策问题。,【例1】最短路径问题。下图给出了一个地图，地图中的每个顶点代表一个城市，两个城市间的一条连线代表道路，连线上的数值代表道路的长度。现在想从城市A到达城市E，怎样走路程最短？最短路程的长度是多少？,【算法分析】把A到E的全过程分成四个阶段，用K表示阶段变量，第1阶段有一个初始状态A，有两条可供选择的支路A-B1、A-B2；第2阶段有两个初始状态B1、B2，B1有三条可供选择的支路，B2有两条可供选择的支路。用DK（XI，X+1J）表示在第K阶段由初始状态XI到下阶段的初始状态X+1J的路径距离，FK（XI）表示从第K阶段的XI到终点E的最短距离，利用倒推的方法，求解A到E的最短距离。,具体计算过程如下：S1：K=4 有 F4（D1）=3，F4（D2）=4，F4（D3）=3；S2：K=3 有 F3（C1）=MIN D3（C1，D1）+F4（D1），D3（C1，D2）+F4（D2）=MIN 5+3，6+4=8 F3（C2）=D3（C2，D1）+F4（D1）=5+3=8 F3（C3）=D3（C3，D3）+F4（D3）=8+3=11 F3（C4）=D3（C4，D3）+F4（D3）=3+3=6S3：K=2 有 F2（B1）=MIN D2（B1，C1）+F3（C1），D2（B1，C2）+F3（C2），D2（B1，C3）+F3(C3)=MIN 1+8,6+8,3+11=9 F2（B2）=MIN D2（B2，C2）+F3（C2），D2（B2，C4）+F3（C4）=MIN 8+8，4+6=10S4：K=1 有 F1（A）=MIN D1（A，B1）+F2（B1），D1（A，B2）+F2（B2）=MIN 5+9，3+10=13 因此由A点到E点的全过程最短路径为AB2C4D3E；最短路程长度为13。从以上过程可以看出，每个阶段中，都求出本阶段的各个初始状态到终点E的最短距离，当逆序倒推到过程起点A时，便得到了全过程的最短路径和最短距离。在上例的多阶段决策问题中，各个阶段采取的决策，一般来说是与阶段有关的，决策依赖于当前状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来的，故有“动态”的含义，我们称这种解决多阶段决策最优化的过程为动态规划程序设计方法。,动态规划的基本概念和基本模型构成,现在我们来介绍动态规划的基本概念。1.阶段和阶段变量：用动态规划求解一个问题时，需要将问题的全过程恰当地分成若干个相互联系的阶段，以便按一定的次序去求解。描述阶段的变量称为阶段变量，通常用K表示，阶段的划分一般是根据时间和空间的自然特征来划分，同时阶段的划分要便于把问题转化成多阶段决策过程，如例题1中，可将其划分成4个阶段，即K=1，2，3，4。2.状态和状态变量：某一阶段的出发位置称为状态，通常一个阶段包含若干状态。一般地，状态可由变量来描述，用来描述状态的变量称为状态变量。如例题1中，C3是一个状态变量。3.决策、决策变量和决策允许集合：在对问题的处理中作出的每种选择性的行动就是决策。即从该阶段的每一个状态出发，通过一次选择性的行动转移至下一阶段的相应状态。一个实际问题可能要有多次决策和多个决策点，在每一个阶段的每一个状态中都需要有一次决策，决策也可以用变量来描述，称这种变量为决策变量。在实际问题中，决策变量的取值往往限制在某一个范围之内，此范围称为允许决策集合。如例题1中，F3（C3）就是一个决策变量。4策略和最优策略：所有阶段依次排列构成问题的全过程。全过程中各阶段决策变量所组成的有序总体称为策略。在实际问题中，从决策允许集合中找出最优效果的策略成为最优策略。5.状态转移方程 前一阶段的终点就是后一阶段的起点，对前一阶段的状态作出某种决策，产生后一阶段的状态，这种关系描述了由k阶段到k+1阶段状态的演变规律，称为状态转移方程。,最优化原理与无后效性,上面已经介绍了动态规划模型的基本组成，现在需要解决的问题是：什么样的“多阶段决策问题”才可以采用动态规划的方法求解。一般来说，能够采用动态规划方法求解的问题，必须满足最优化原理和无后效性原则：1、动态规划的最优化原理。作为整个过程的最优策略具有：无论过去的状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略的性质。也可以通俗地理解为子问题的局部最优将导致整个问题的全局最优，即问题具有最优子结构的性质，也就是说一个问题的最优解只取决于其子问题的最优解，而非最优解对问题的求解没有影响。在例题1最短路径问题中，A到E的最优路径上的任一点到终点E的路径，也必然是该点到终点E的一条最优路径，即整体优化可以分解为若干个局部优化。2、动态规划的无后效性原则。所谓无后效性原则，指的是这样一种性质：某阶段的状态一旦确定，则此后过程的演变不再受此前各状态及决策的影响。也就是说，“未来与过去无关”，当前的状态是此前历史的一个完整的总结，此前的历史只能通过当前的状态去影响过程未来的演变。在例题1最短路径问题中，问题被划分成各个阶段之后，阶段K中的状态只能由阶段K+1中的状态通过状态转移方程得来，与其它状态没有关系，特别与未发生的状态没有关系，例如从Ci到E的最短路径，只与Ci的位置有关，它是由Di中的状态通过状态转移方程得来，与E状态，特别是A到Ci的路径选择无关，这就是无后效性。由此可见，对于不能划分阶段的问题，不能运用动态规划来解；对于能划分阶段，但不符合最优化原理的，也不能用动态规划来解；既能划分阶段，又符合最优化原理的，但不具备无后效性原则，还是不能用动态规划来解；误用动态规划程序设计方法求解会导致错误的结果。,动态规划设计方法的一般模式,动态规划所处理的问题是一个多阶段决策问题，一般由初始状态开始，通过对中间阶段决策的选择，达到结束状态；或倒过来，从结束状态开始，通过对中间阶段决策的选择，达到初始状态。这些决策形成一个决策序列，同时确定了完成整个过程的一条活动路线，通常是求最优活动路线。动态规划的设计都有着一定的模式，一般要经历以下几个步骤：1、划分阶段 按照问题的时间或空间特征，把问题划分为若干个阶段。在划分阶段时，注意划分后的阶段一定是有序的或者是可排序的，否则问题就无法求解。2、确定状态和状态变量 将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要满足无后效性。3、确定决策并写出状态转移方程 因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以如果确定了决策，状态转移方程也就可以写出。但事实上常常是反过来做，根据相邻两段的各个状态之间的关系来确定决策。4、寻找边界条件 给出的状态转移方程是一个递推式，需要一个递推的终止条件或边界条件。,【例1】对应的Pascal程序如下：var d:array1.4,1.4,1.4 of integer;f:array1.5,1.4 of integer;i,j,k,min:integer;begin fillchar(d,sizeof(d),0);d1,1,1:=5;d1,1,2:=3;d2,1,1:=1;d2,1,2:=6;d2,1,3:=3;d2,2,2:=8;d2,2,4:=4;d3,1,1:=5;d3,1,2:=6;d3,2,1:=5;d3,3,3:=8;d3,4,3:=3;d4,1,1:=3;d4,2,1:=4;d4,3,1:=3;fillchar(f,sizeof(f),255);f5,1:=0;for i:=4 downto 1 do for j:=1 to 4 do for k:=1 to 4 do if di,j,k 0 then if fi,j di,j,k+fi+1,k then fi,j:=di,j,k+fi+1,k;writeln(f1,1);readln;end.,第二节 动态规划与递推 动态规划是最优化算法,由于动态规划的“名气”如此之大，以至于很多人甚至一些资料书上都往往把一种与动态规划十分相似的算法，当作是动态规划。这种算法就是递推。实际上，这两种算法还是很容易区分的。按解题的目标来分，信息学试题主要分四类：判定性问题、构造性问题、计数问题和最优化问题。我们在竞赛中碰到的大多是最优化问题，而动态规划正是解决最优化问题的有力武器，因此动态规划在竞赛中的地位日益提高。而递推法在处理判定性问题和计数问题方面也是一把利器。下面分别就两个例子，谈一下递推法和动态规划在这两个方面的联系。,【例2】数塔问题（IOI94）有形如图所示的数塔，从顶部出发，在每一结点可以选择向左走或是向右走，一起走到底层，要求找出一条路径，使路径上的值最大。,这道题如果用枚举法，在数塔层数稍大的情况下（如40），则需要列举出的路径条数将是一个非常庞大的数目。如果用贪心法又往往得不到最优解。在用动态规划考虑数塔问题时可以自顶向下的分析，自底向上的计算。从顶点出发时到底向左走还是向右走应取决于是从左走能取到最大值还是从右走能取到最大值，只要,左右两道路径上的最大值求出来了才能作出决策。同样的道理下一层的走向又要取决于再下一层上的最大值是否已经求出才能决策。这样一层一层推下去，直到倒数第二层时就非常明了。所以实际求解时，可从底层开始，层层递进，最后得到最大值。实际求解时应掌握其编程的一般规律，通常需要哪几个关键数组来存储变化过程这一点非常重要。一般说来，很多最优化问题都有着对应的计数问题；反过来，很多计数问题也有着对应的最优化问题。因此，我们在遇到这两类问题时，不妨多联系、多发展，举一反三，从比较中更深入地理解动态规划的思想。其实递推和动态规划这两种方法的思想本来就很相似，也不必说是谁借用了谁的思想。关键在于我们要掌握这种思想，这样我们无论在用动态规划法解最优化问题，或是在用递推法解判定型、计数问题时，都能得心应手、游刃有余了。,【解法一】（逆推法）【算法分析】贪心法往往得不到最优解：本题若采用贪心法则：13-11-12-14-13，其和为63,但存在另一条路：13-8-26-15-24，其和为86。贪心法问题所在：眼光短浅。动态规划求解：动态规划求解问题的过程归纳为：自顶向下的分析，自底向上计算。其基本方法是：划分阶段：按三角形的行，划分阶段，若有n行，则有n-1个阶段。A从根结点13出发，选取它的两个方向中的一条支路，当到倒数第二层时，每个结点其后继仅有两个结点，可以直接比较，选择最大值为前进方向，从而求得从根结点开始到底端的最大路径。B自底向上计算：（给出递推式和终止条件）从底层开始，本身数即为最大数；倒数第二层的计算，取决于底层的数据：12+6=18，13+14=27，24+15=39，24+8=32；倒数第三层的计算，取决于底二层计算的数据：27+12=39，39+7=46，39+26=65 倒数第四层的计算，取决于底三层计算的数据：46+11=57，65+8=73 最后的路径：138261524,C数据结构及算法设计 图形转化：直角三角形，便于搜索：向下、向右 用三维数组表示数塔：ax,y,1表示行、列及结点本身数据,ax,y,2能够取得最大值,ax,y,3表示前进的方向0向下，1向右；算法：数组初始化，输入每个结点值及初始的最大路径、前进方向为0；从倒数第二层开始向上一层求最大路径，共循环N-1次；从顶向下，输出路径：究竟向下还是向右取决于列的值，若列的值比原先多1则向右，否则向下。,【参考程序】program ex14_2_1;var a:array1.50,1.50,1.3 of longint;x,y,n:integer;begin write(please input the number of rows:);readln(n);for x:=1 to n do/输入数塔的初始值 for y:=1 to x do begin read(ax,y,1);ax,y,2:=ax,y,1;ax,y,3:=0/路径走向，默认向下 end;,for x:=n-1 downto 1 do for y:=1 to x do if ax+1,y,2ax+1,y+1,2 then/选择路径，保留最大路径值 begin ax,y,2:=ax,y,2+ax+1,y,2;ax,y,3:=0 end else begin ax,y,2:=ax,y,2+ax+1,y+1,2;ax,y,3:=1 end;writeln(max=,a1,1,2);/输出数塔最大值 y:=1;for x:=1 to n-1 do/输出数塔最大值的路径 begin write(ax,y,1,-);y:=y+ax,y,3;/下一行的列数 end;writeln(an,y,1)end.输入：5/数塔层数1311 812 7 266 14 15 812 7 13 24 11,输出结果：max=86 13-8-26-15-24,【解法二】（顺推法）【算法分析】此题贪心法往往得不到最优解，例如13-11-12-14-13其路径的值为63，但这不是最优解。穷举搜索往往是不可能的，当层数N=100时，路径条数P=299这是一个非常大的数，即使用世界上最快的电子计算机，也不能在规定时间内计算出来。对这道题唯一正确的方法是动态规划。如果得到一条由顶到底的某处的一条最佳路径，那么对于该路径上的每一个中间点来说，由顶点至该中间点的路径所经过的数字和也为最大。因此本题是一个典型的多阶段决策最优化问题。在本题中仅要求输出最优解，为此我们设置了数组Ai,j保存三角形数塔，Bi,j保存状态值，按从上往下方式进行求解。阶段i：以层数来划分阶段，由从上往下方式计算层数1层数N（1in）；因此可通过第一重循环 for i:=1 to n do begin 枚举每一阶段；状态Bi,j：由于每个阶段中有多个状态，因此可通过第二重循环 for j:=1 to i do begin 求出每个阶段的每个状态的最优解Bi,j；决 策：每个状态最多由上一层的两个结点连接过来，因此不需要做循环。【参考程序】program ex14_2_2;Var a,b:array1.100,0.100 of word;i,j,n:integer;max:word;,begin write(N=);readln(n);fillchar(a,sizeof(a),0);for i:=1 to n do/输入数塔的初始值 begin for j:=1 to i do read(ai,j);readln;end;b:=a;b1,1:=a1,1;for i:=2 to n do/选择路径，保留最大路径值 for j:=1 to i do if bi-1,j-1 bi-1,j then bi,j:=bi-1,j-1+bi,j else bi,j:=bi-1,j+bi,j;max:=0;for i:=1 to n do if bn,i max then max:=bn,i;/在第n行中找出数塔最大值 writeln(Max=,max);/输出数塔最大值 readln;end.,【例3】求最长不下降序列问题描述：设有由n个不相同的整数组成的数列，记为:b(1)、b(2)、b(n)且b(i)b(j)(ij)，若存在i1b(n)则存在长度为1的不下降序列b(n-1)或b(n)。3一般若从b(i)开始，此时最长不下降序列应该按下列方法求出:在b(i+1),b(i+2),b(n)中，找出一个比b(i)大的且最长的不下降序列，作为它的后继。数据结构：为算法上的需要，定义一个整数类型二维数组b(N,3)1b(I,1)表示第I个数的数值本身；2b(I,2)表示从I位置到达N的最长不下降序列长度,3b(I,3)表示从I位置开始最长不下降序列的下一个位置，若bI,3=0则表示后面没有连接项。,求解过程：从倒数第二项开始计算，后面仅有1项，比较一次，因6315，不符合要求，长度仍为1。从倒数第三项开始其后有2项，需做两次比较，得到目前最长的不下降序列为2，如下表：,一般处理过程是：在i+1,i+2,n项中，找出比bI,1大的最长长度L以及位置K;若L0，则bI,2:=L+1;bI,3:=k;最后本题经过计算，其数据存储表如下：,初始化:for i:=1 to n do begin read(bi,1);bi,2:=1;bi,3:=0;end;下面给出求最长不下降序列的算法:for i:=n-1 downto 1 do begin L:=0;k:=0;for j:=i+1 to n do if(bj,1bi,1)and(bj,2L)then begin L:=bj,2;k:=j;end;if L0 then begin bi,2:=L+1;bi,3:=k;end;end;,下面找出最长不下降序列：k:=1;for j:=1 to n do if bj,2bk,2 then k:=j;最长不下降序列长度为B(k,2)序列 while k0 do begin write(bk,1:4);k:=bk,3;end;,【参考程序】program ex14_3;var n,i,L,k,j:integer;b:array1.100,1.3of integer;begin writeln(input n:);readln(n);for i:=1 to n do/输入序列的初始值 begin read(bi,1);bi,2:=1;bi,3:=0;end;,for i:=n-1 downto 1 do/求最长不下降序列 begin L:=0;k:=0;for j:=i+1 to n do if(bj,1bi,1)and(bj,2L)then begin L:=bj,2;k:=j;end;if L0 then begin bi,2:=L+1;bi,3:=k;end;end;k:=1;for j:=1 to n do/求最长不下降序列的起始位置 if bj,2bk,2 then k:=j;writeln(max=,bk,2);/输出结果 while k0 do/输出最长不下降序列 begin write(bk,1:4);k:=bk,3;end;writeln;readln;end.,程序运行结果：输入：1413 7 9 16 38 24 37 18 44 19 21 22 63 15输出：max=87 9 16 18 19 21 22 63,【例4】拦截导弹1(Noip1999)某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭，由于该系统还在试用阶段。所以只有一套系统，因此有可能不能拦截所有的导弹。输入导弹依次飞来的高度(雷达给出的高度不大于30000的正整数)。计算这套系统最多能拦截多少导弹。输入：N颗依次飞来的导弹高度，（导弹个数=1000）。输出：一套系统最多拦截的导弹数，并依次打印输出被拦截导弹的高度。在本题中不仅要求输出最优解，而且还要求输出最优解的形成过程。为此，我们设置了一张记忆表Ci，在按从后往前方式求解的过程中，将每一个子问题的最佳决策保存起来，避免在输出方案时重复计算。阶段i：由右而左计算导弹n导弹1中可拦截的最多导弹数（1in）；状态Bi：由于每个阶段中仅一个状态，因此可通过一重循环 for i:=n-1 downto 1 do 枚举每个阶段的状态Bi；决策k：在拦截导弹i之后应拦截哪一枚导弹可使得Bi最大（i+1kn），1 2 3 4 5 6 7 8 9 10 11 12 13 14 I13 7 9 16 38 24 37 18 44 19 21 22 63 15 AI/高度2 1 1 2 4 3 3 2 3 2 2 2 2 1 BI/可拦截数2 0 0 14 6 8 8 14 10 14 14 14 14 0 CI/再拦截,【参考程序】（逆推法）program ex14_4_1;Var a,b,c:array1.1000 of longint;n,i,j,k,max:longint;begin n:=0;/初始化，读入数据 while not eoln do begin/eoln：行结束标志 inc(n);read(an);bn:=1;cn:=0;end;readln;for i:=n-1 downto 1 do begin/枚举每一个阶段的状态，设导弹i被拦截 max:=0;k:=0;for j:=i+1 to n do/枚举决策，计算最佳方案中拦截的下一枚导弹 if(aj max)then begin max:=bj;,k:=j;end;bi:=max+1;ci:=k;/若导弹i之后拦截导弹k为最佳方案，则记下 end;max:=0;for i:=1 to n do/枚举求出一套系统能拦截的最多导数 if bi max then begin max:=bi;k:=i;end;writeln(Max=,bk);/打印输出结果 while k 0 do begin write(ak:5);k:=ck;end;readln;end.,【例5】拦截导弹2(Noip1999)某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。样例：INPUT OUTPUT389 207 155 300 299 170 158 65 6（最多能拦截的导弹数）2（要拦截所有导弹最少要配备的系统数）【算法分析】第一问即经典的最长不下降子序列问题，可以用一般的DP算法，也可以用高效算法，但这个题的数据规模好像不需要。高效算法是这样的：用ax表示原序列中第x个元素，bx表示长度为x的不下降子序列的最后一个元素的最小值，b数组初值为无穷大。容易看出，这个数组是递减的（当然可能有相邻两个元素相等）。当处理第ax时，用二分法查找它可以连接到长度最大为多少的不下降子序列后（即与部分bx比较）。假设可以连到长度最大为y的不下降子序列后，则by+1:=min(by+1,ax)。最后，b数组被赋值的元素最大下标就是第一问的答案。由于利用了二分查找，这种算法的复杂度为O(nlogn)，优于一般的O(n2)。第二问用贪心法即可。每颗导弹来袭时，使用能拦截这颗导弹的防御系统中上一次拦截导弹高度最低的那一套来拦截。若不存在符合这一条件的系统，则使用一套新系统。,【参考程序】（顺推法）program tju1004;const max=20;var a,b,h:array1.maxof longint;i,j,m,n,x,max:integer;begin repeat inc(i);max:=0;read(ai);for j:=1 to i-1 do/计算前i-1个导弹最佳拦截的方案 if aj=ai then if bjmax then max:=bj;bi:=max+1;/在前i-1个导弹最佳方案+1 if bim then m:=bi;x:=0;for j:=1 to n do/计算由哪一套系统拦截导弹 if hj=ai then if x=0 then x:=j else if hjhx then x:=j;if x=0 then begin inc(n);x:=n;end;/新增一套导弹拦截系统 hx:=ai;until seekeof;/eof：文件结束标志 writeln(m,n);end.,经过计算，其数据存储表如下,【例6】下图表示城市之间的交通路网，线段上的数字表示费用，单向通行由A-E。试用动态规划的最优化原理求出A-E的最省费用。,交通图1,交通图2,如图：求v1到v10的最短路径长度及最短路径。,【样例输入】short.in100 2 5 1 0 0 0 0 0 00 0 0 0 12 14 0 0 0 00 0 0 0 6 10 4 0 0 00 0 0 0 13 12 11 0 0 00 0 0 0 0 0 0 3 9 00 0 0 0 0 0 0 6 5 00 0 0 0 0 0 0 0 10 00 0 0 0 0 0 0 0 0 50 0 0 0 0 0 0 0 0 20 0 0 0 0 0 0 0 0 0【样例输出】short.outminlong=191 3 5 8 10,【算法分析】逆推法设f(i)表示点i到v10的最短路径长度，则 f(10)=0 f(i)=min ai,x+f(x)当ai,x0,ix=n,【参考程序】（逆推法）program short;var a:array1.100,1.100 of integer;f,c:array1.100 of integer;i,j,n,x:integer;begin assign(input,short.in);assign(output,short.out);reset(input);rewrite(output);readln(n);for i:=1 to n do/输入各个城市之间距离 for j:=1 to n do read(ai,j);for i:=1 to n do fi:=maxint;/初始化，默认每一个城市到达终点都是maxint fn:=0;for i:=n-1 downto 1 do/从终点往前逆推，计算最短路径 for x:=i+1 to n do/若fx=maxint表示城市x到终点城市不通 if(ai,x0)and(fxmaxint)and(fiai,x+fx)/ai,x0表示城市i和城市x通路 then begin fi:=ai,x+fx;ci:=x end;/城市i到终点最短路径的值 writeln(minlong=,f1);/输出最短路径的值 x:=1;while x0 do/输出路过的各个城市 begin write(x:5);x:=cx;end;close(input);close(output);end.,【例7】挖地雷（Mine.pas）【问题描述】在一个地图上有N个地窖（N=200）,每个地窖中埋有一定数量的地雷。同时，给出地窖之间的连接路径，并规定路径都是单向的。某人可以从任一处开始挖地雷，然后沿着指出的连接往下挖（仅能选择一条路径），当无连接时挖地雷工作结束。设计一个挖地雷的方案，使他能挖到最多的地雷。【输入格式】N/地窖的个数 W1，W2，WN/每个地窖中的地雷数 X1，Y1/表示从X1可到Y1 X2，Y2 0，0/表示输入结束【输出格式】K1K2Kv/挖地雷的顺序 MAX/最多挖出的地雷数,【输入样例】Mine.in65 10 20 5 4 51 21 42 4,3 44 54 65 60 0【输出样例】Mine.out3-4-5-634,【算法分析】本题是一个经典的动态规划问题。很明显，题目规定所有路径都是单向的，所以满足无后效性原则和最优化原理。设W(i)为第i个地窖所藏有的地雷数，A（i,j）表示第i个地窖与第j个地窖之间是否有通路，F(i)为从第i个地窖开始最多可以挖出的地雷数，则有如下递归式：F(i)=MAX W(i)+F(j)(ij=n,A(i,j)=true)边界：F(n)=W(n)于是就可以通过递推的方法，从后F(n)往前逐个找出所有的F(i)，再从中找一个最大的即为问题2的解。对于具体所走的路径（问题1），可以通过一个向后的链接来实现。,【参考程序】program Mine;var f:array1.200,1.2 of longint;a:array1.200,1.200 of boolean;w:array1.200 of longint;n,i,j,x,y,L,k,max:longint;begin assign(input,mine.in);reset(input);assign(output,mine.out);rewrite(output);fillchar(a,sizeof(a),false);fillchar(f,sizeof(f),0);readln(n);for i:=1 to n do/输入每个地窖中的地雷数 read(wi);readln;repeat readln(x,y);/表示从X可到Y if(x0)and(y0)then ax,y:=true;until(x=0)and(y=0);fn,1:=wn;/从后F(n)往前逐个找出所有的F(i),for i:=n-1 downto 1 do begin L:=0;k:=0;for j:=i+1 to n do if ai,j and(fj,1L)then begin L:=fj,1;k:=j;end;fi,1:=L+wi;/保存从第i个地窖起能挖到最大地雷数 fi,2:=k;/k地窖是i地窖最优路径 end;k:=1;for j:=2 to n do/计算最多挖出的地雷数 if fj,1fk,1 then k:=j;max:=fk,1;write(k);k:=fk,2;while k0 do/输出挖地雷的顺序 begin write(-,k);k:=fk,2;end;writeln;writeln(max);/输出最多挖出的地雷数 close(input);close(output);end.,【例8】轮船问题(ship.pas)【问题描述】某国家被一条河划分为南北两部分，在南岸和北岸总共有N对城市，每一城市在对岸都有唯一的友好城市，任何两个城市都没有相同的友好城市。每一对友好城市都希望有一条航线来往，于是他们向政府提出了申请。由于河终年有雾，政府决定允许开通的航线就互不交叉（如果两条航线交叉，将有很大机会撞船）。兴建哪些航线以使在安全条件下有最多航线可以被开通。【输入格式】输入文件(ship.in):包括了若干组数据，每组数据格式如下：第一行两个由空格分隔的整数x，y，10=x=6000，10=y=100。x表示河的长度而y表示宽。第二行是一个整数N(1=N=5000)，表示分布在河两岸的城市对数。接下来的N行每行有两个由空格分隔的正数C，D（C、D=x，描述每一对友好城市与河起点的距离，C表示北岸城市的距离而D表示南岸城市的距离。在河的同一边，任何两个城市的位置都是不同的。【输出格式】输出文件(ship.out)：要在连续的若干行里给出每一组数据在安全条件下能够开通的最大航线数目。,【输入输出样例】,Ship.in30 4 54 52 45 21 33 1,Ship.out3,【算法分析】我们将每对友好城市看成一条线段，则这道题的描述化为：有N条线段，问最少去掉多少条线，可以使剩下的线段互不交叉？第一，以北岸为线的起点而南岸为线的终点；先将所有的线按照起点坐标值从小到大排序，按照每条线的终点坐标计算交叉数：求线I的交叉数JI，则检查所有1.I-1条线，若线J(1=J I)的终点值大于线I的终点值，则线I与线J相交。JI与JJ同时加1。整个搜索量最大为5000*5000。第二，将J数组从大到小排序，每删除一条线，则将与之相交的线的J值减1，重复这个过程，直到所有J值都为0。此时剩下的线则全不交叉。,如上数据，则可得下面结果：,此时，1、2、3航线的交叉数都一样，如果删去的是3、5线，则剩下的1、2、4线互不相交，最多航线数为3；但如果删去的是2、3，则还要删去第5线才符合要求，此时的最多航线数为2，不是最优解。于是，我们从上面的分析中再深入，将航线按起点坐标排好序后，如上所述，在本题中，只要线J的起点小于线I的起点，同时它的终点也小于线I的终点，则线J和线I不相交。因此，求所有线中最多能有多少条线不相交，实际上是从终点坐标值数列中求一个最长不下降序列。这就把题目转化为一个非常典型的动态规划题目了。求最长不下降序列的规划方程如下：L(Si)=maxL(Sj)+1；1=j i且 Sj Si。Si为航线的终点坐标值。从以上分析过程可以得出：当我们拿到一道题时，不要急于求解，而应先将题目的表面现象一层层象剥竹笋一样去掉，只留下最实质的内容。这时再来设计算法，往往能事半功倍。,第三节 历届NOIP动态规划试题,【例题1】骑士游历问题 设有一个n*m的棋盘(2n50，2m50)，如图1。在棋盘上任一点有一个中国象棋马，,马走的规则为：1.马走日字 2.马只能向右走。即图所示：,当N，M 给出之后，同时给出马起始的位置和终点的位置，试找出从起点到终点的所有路径的数目。例如：(N=10，M=10)，(1，5)(起点)，(3，5)(终点)。应输出2(即由(1，5)到(3，5)共有2条路径，如图：,【输入格式】n，m，x1，y1，x2，y2(分别表示n，m，起点坐标，终点坐标)【输出格式】路径数目(若不存在从起点到终点的路径，输出0),【算法分析】使用回溯法同样可以计算路径数目。只要将起点（1，1）和终点（n，m）调整为（x1，y1）、（x2，y2），并在回溯程序(search(k，x，y)中，将马跳到目的地时由退出程序（halt）改为回溯（exit）即可。但问题是搜索效率太低，根本不可能在较短的时间内出解。本题并不要求每一条路径的具体走法。在这种情况下，是否非得通过枚举所有路径方案后才能得出路径数目，有没有一条简便和快效的“捷径”呢。从(x1，y1)出发，按照由左而右的顺序定义阶段的方向。位于（x，y）左方且可达（x，y）的跳马位置集合都是（x，y）的子问题，起点至（x，y）的路径数实际上等于起点至这些位置集的路径数之和（图4）。,如此一来，状态转移关系便凸显出来。设状态转移方程map，其中mapi，j为起点（x1，y1）至（i，j）的路径数目。由于棋盘规模的上限为50*50，可能导致路径数目大得惊人，因此不妨设map数组的元素类型为extended。初始时，除mapx1，y1=1外其余为。显然,我们采用动态程序设计的方法计算起点(x1，y1)至终点（x2，y2）的路径数目mapx2，y2：阶段j：中国象棋马当前的列位置(y1jy2)；状态i：中国象棋马在j列的行位置（1in）；决策k：中国象棋马在（i，j）的起跳方向(1k4)；,计算过程如下：fi