第5讲 动态规划的题型

1、动态规划的题型动态规划的题型计算所有方案计算所有方案计算一些阶段性明显、但不具备最优子结计算一些阶段性明显、但不具备最优子结构特征的问题构特征的问题多进程的最优化决策问题多进程的最优化决策问题双重动态规划双重动态规划自上而下的动态规划自上而下的动态规划动态规划前进行预处理动态规划前进行预处理状态的定义是提高效率的关键状态的定义是提高效率的关键一、计算所有方案 对于一些阶段性强、但不属于最优化的问题，是对于一些阶段性强、但不属于最优化的问题，是否也可以借助动态规划方法呢？如果我们可以找否也可以借助动态规划方法呢？如果我们可以找出状态转移的关系，并在状态转移方程出状态转移的关系，并在状态转移方程中

2、去掉中去掉最佳性要求最佳性要求（minmin或或maxmax），将），将扩展子状态扩展子状态的所有行动作为决策，则可以例举出由初始状态的所有行动作为决策，则可以例举出由初始状态至目标状态的所有方案。至目标状态的所有方案。例题2 过河卒 如图，如图，A A点有一个过河卒，需要走到目标点有一个过河卒，需要走到目标B B点。点。卒行走的规则：可以向下、或者向右。卒行走的规则：可以向下、或者向右。 同时在棋盘上的任一点有一个对方的马（如上图的同时在棋盘上的任一点有一个对方的马（如上图的C C点）点）, ,该马该马所在的点和所有跳跃一步可达的点称为对方马的控制点。例如所在的点和所有跳跃一步可达的点称为对

3、方马的控制点。例如上图上图C C点上的马可以控制点上的马可以控制8 8个点（图中的个点（图中的P1P1，P2.P8P2.P8）。卒不能）。卒不能通过对方马的控制点。通过对方马的控制点。 棋盘用坐标表示，棋盘用坐标表示，A A点（点（0 0，0 0）、）、B B点（点（n n，m m）(n,m(n,m为不超过为不超过2020的整数的整数, ,并由键盘输入并由键盘输入) )，同样马的位置坐标是需要给出的（约定：，同样马的位置坐标是需要给出的（约定：CACA，同时，同时CBCB）。现在要求你计算出卒从）。现在要求你计算出卒从A A 点能够到达点能够到达B B点点的路径的条数。的路径的条数。输输 入：

4、入：键盘输入键盘输入B B点的坐标点的坐标(n,m)(n,m)以及对方马的坐标（以及对方马的坐标（X X，Y Y）输输 出：出：屏幕输出一个整数（路径的条数）。屏幕输出一个整数（路径的条数）。输入输出样例：输入输出样例：输入：输入：3 3 2 23 3 2 2输出：输出：0 0按照题意，对方的马所在的点和所有跳跃一步可达的点称为对方马的控制点，卒按照题意，对方的马所在的点和所有跳跃一步可达的点称为对方马的控制点，卒不能通过对方马的控制点。在卒出发之前，必须计算对方马的所有控制点。不能通过对方马的控制点。在卒出发之前，必须计算对方马的所有控制点。显然，若（显然，若（0，0）或（）或（n,m）为控

5、制点，则输出路径数为）为控制点，则输出路径数为0。设。设constmove:array1.8,1.2ofinteger=(1,-2),(1,2),(2,1),(2,-1),(-1,2),(-1,-2),(-2,1),(-2,-1)； movek，1.2为马为马沿沿k方向跳跃一步的水平增量和垂直增量方向跳跃一步的水平增量和垂直增量varlist:array-1.20,-1.20 of comp；路径数序列，其中路径数序列，其中listi,j为卒从为卒从(0,0)到到(i,j)的路径数的路径数can:array0.20,0.20 of boolean； 点点(i,j)允许卒通行的标志允许卒通行的标

6、志马的初始位置为（马的初始位置为（x,y）。我们按照下述方式计算）。我们按照下述方式计算can序列：序列：canx,y false； 对方马所在的点为控制点对方马所在的点为控制点for i1 to 8 do begin从（从（x，y）出发，沿）出发，沿8个跳马方向计算控制点个跳马方向计算控制点jx+movei,1； 计算计算i方向的跳马位置方向的跳马位置(j，k)ky+movei,2；if (j=0) and (k=0) and (j=n) and (k=m) 若（若（j,k）在界内，则为控制点）在界内，则为控制点then canj,k false；end；forif (not can0,0)

7、or(not cann,m) 若卒的起点和终点为控制点，则输出路径数若卒的起点和终点为控制点，则输出路径数0 then writeln(0)else begin 计算和输出卒从（计算和输出卒从（0，0）走到（）走到（n,m）点的路径数）点的路径数listn,m； end；else1 1、计算对方马的控制点、计算对方马的控制点 我们按照由上而下、由左而右的顺序，将卒可能到达的每一我们按照由上而下、由左而右的顺序，将卒可能到达的每一个位置（个位置（i,ji,j）(0in(0in，0jm)0jm)设为阶段设为阶段, ,显然这样做，可以显然这样做，可以取消对状态的枚举。取消对状态的枚举。 首 先 ，

8、将 卒 的 出 发 点 （首 先 ， 将 卒 的 出 发 点 （ 0 0 ， 0 0 ） 的 路 径 数 设 为） 的 路 径 数 设 为 1 1（list0,01list0,01），并将该位置设为控制点（），并将该位置设为控制点（can0,0 can0,0 falsfals）。然后从（）。然后从（0 0，0 0）出发，按照由上而下、由左而右的顺）出发，按照由上而下、由左而右的顺序计算卒经过每一个可行点的路径数。若（序计算卒经过每一个可行点的路径数。若（i i，j j）为可行点，则）为可行点，则卒可由上侧的（卒可由上侧的（i-1,ji-1,j）和左侧的（）和左侧的（i,j-1i,j-1）进入该

9、点。将这两点）进入该点。将这两点的路径数加起来，即为从（的路径数加起来，即为从（0 0，0 0）走到（）走到（i i，j j ）的路径数，即）的路径数，即listi,j=listi-1,j+listi,j-1listi,j=listi-1,j+listi,j-1（i i，j j）非控制点）非控制点依次类推，最后得出的依次类推，最后得出的listn,mlistn,m即为问题的解。即为问题的解。2 2、计算和输出卒从（、计算和输出卒从（0 0，0 0）走到（）走到（n,mn,m）点的路径条数）点的路径条数由此得出算法：由此得出算法：fillchar(list,sizeof(list),0)fill

10、char(list,sizeof(list),0)； 路径数序列初始化路径数序列初始化 list0,01list0,01； 卒从（卒从（0 0，0 0）出发的路径数为）出发的路径数为1 1，该位置不，该位置不再允许卒通行再允许卒通行 can0,0 falsecan0,0 false； for i0 to n dofor i0 to n do对于每个可行点对于每个可行点, ,小兵要么从左侧、要么小兵要么从左侧、要么从上方走到从上方走到, ,由此计算从由此计算从(0,0)(0,0)到到(i,j)(i,j)的路径数的路径数 for j0 to m do if cani,jthen listi,jli

11、sti- for j0 to m do if cani,jthen listi,jlisti-1,j+listi,j-11,j+listi,j-1；输出卒从（输出卒从（0 0，0 0）走到（）走到（n,mn,m）点的路径条数）点的路径条数listn,mlistn,m；2 2、计算和输出卒从（、计算和输出卒从（0 0，0 0）走到（）走到（n,mn,m）点的路径条数）点的路径条数例题3 n重幂 设给定设给定n n个变量个变量x1,x2,xn,x1,x2,xn,将这些变量依序作底和各层幂，可将这些变量依序作底和各层幂，可得出左图的得出左图的n n重幂。这里将重幂。这里将n n重幂看作是不确定的，当

12、在其中加入重幂看作是不确定的，当在其中加入适当的括号后，才能成为一个确定的适当的括号后，才能成为一个确定的n n重幂。通常将重幂。通常将n n重幂的理解重幂的理解为右图所示的形状：为右图所示的形状：123xxxxn不同的加括号方式导致不同的不同的加括号方式导致不同的n n重幂。例如，当重幂。例如，当n=4n=4时，时，x1,x2,x3,x4x1,x2,x3,x4的全部的全部4 4重幂有重幂有5 5个。试设计一个算法，对个。试设计一个算法，对n n个变量个变量计算出有多少个不同的计算出有多少个不同的n n重幂重幂。状态转移方程状态转移方程 设设cici为为i i个变量计算出的不同的个变量计算出的

13、不同的i i重幂的重幂的个数。个数。 C1=1C1=1； ci= ci= ； 目标是计算目标是计算cncn。注意高精度运算。注意高精度运算11*ijjicjcreadln(n)readln(n)； 读变量数读变量数 fillchar(c,sizeof(c),0);fillchar(c,sizeof(c),0);creat(c1,1);creat(c1,1);建立值为建立值为1 1的的c c数组数组for i:=2 to n dofor i:=2 to n do for j:=1 to i-1 do for j:=1 to i-1 do begin begin multiply2(cj,ci-j

14、,a); multiply2(cj,ci-j,a);acjacjci-jci-j plus(ci,a,b);plus(ci,a,b);bci+abci+a ci:=bci:=b end; end; 输出输出cncn三、双重动态规划三、双重动态规划 当问题的决策为复合决策（也就是一些子决当问题的决策为复合决策（也就是一些子决策的排列）时，将每个复合决策细化成若干个策的排列）时，将每个复合决策细化成若干个子决策，并在每个子决策后面增设一个状态。子决策，并在每个子决策后面增设一个状态。这样，后面的子决策只在前面的子决策达到最这样，后面的子决策只在前面的子决策达到最优解时才进行转移优解时才进行转移 。

15、 使用使用“双重动态规划的条件：即原来每个复双重动态规划的条件：即原来每个复合决策的各个子决策之间也满足最优化原理和合决策的各个子决策之间也满足最优化原理和无后效性。即符合最优决策的子决策也是最优无后效性。即符合最优决策的子决策也是最优决策，前面的子决策不影响后面的子决策。决策，前面的子决策不影响后面的子决策。例题5 金明的预算方案 金明今天很开心，家里购置的新房就要领钥匙了，新房里有一金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间金明自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天间金明自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：对他说：“你的房间需要购买哪些物品，怎么

16、布置，你说了算，你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过只要不超过N N元钱就行元钱就行”。今天一早，金明就开始做预算了，。今天一早，金明就开始做预算了，他把想买的物品分为两类：主件与附件，附件是从属于某个主他把想买的物品分为两类：主件与附件，附件是从属于某个主件的，下表就是一些主件与附件的例子：件的，下表就是一些主件与附件的例子：主件附件电脑打印机，扫描仪书柜图书 如果要买归类为附件的物品，必须先买该附件所属如果要买归类为附件的物品，必须先买该附件所属的主件。每个主件可以有的主件。每个主件可以有0 0个、个、1 1个或个或2 2个附件。附件不个附件。附件不再有从属于自己的附件

17、。金明想买的东西很多，肯定会再有从属于自己的附件。金明想买的东西很多，肯定会超过妈妈限定的超过妈妈限定的N N元。于是，他把每件物品规定了一个元。于是，他把每件物品规定了一个重要度，分为重要度，分为5 5等：用整数等：用整数1515表示，第表示，第5 5等最重要。他等最重要。他还从因特网上查到了每件物品的价格（都是还从因特网上查到了每件物品的价格（都是1010元的整数元的整数倍）。他希望在不超过倍）。他希望在不超过N N元（可以等于元（可以等于N N元）的前提下，元）的前提下，使每件物品的价格与重要度的乘积的总和最大。使每件物品的价格与重要度的乘积的总和最大。 设第设第j j件物品的价格为件物

18、品的价格为vjvj，重要度为，重要度为wjwj，共选中，共选中了了k k件物品，编号依次为件物品，编号依次为j1j1，j2j2，jkjk，则所求的，则所求的总和为：总和为：vj1vj1* *wj1+vj2wj1+vj2* *wj2+ +vjkwj2+ +vjk* *wjkwjk。（其中（其中* *为乘号）为乘号）请你帮助金明设计一个满足要求的购物单。请你帮助金明设计一个满足要求的购物单。【输入文件】输入文件【输入文件】输入文件budget.in budget.in 的第的第1 1行，为两个正行，为两个正整数，用一个空格隔开：整数，用一个空格隔开： N mN m（其中（其中N N（3200032

19、000）表示总钱数，）表示总钱数，m m（6060）为希望购买物品的个数）为希望购买物品的个数） 从第从第2 2行到第行到第m+1m+1行，第行，第j j行给出了编号为行给出了编号为j-1j-1的物的物品的基本数据，每行有品的基本数据，每行有3 3个非负整数个非负整数 v p qv p q（其中（其中v v表示该物品的价格（表示该物品的价格（v10000v0q0，表示该物品为附件，表示该物品为附件，q q是所属主件的编号）是所属主件的编号）【输出文件】输出文件【输出文件】输出文件budget.outbudget.out只有一个正整数，只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和

20、的为不超过总钱数的物品的价格与重要度乘积的总和的最大值（最大值（200000200000）。）。题目大意 给出购买总费用M和N件物品，每件物品的特性有：价格、重要度、以及是主件还是附件。对于每个附件，必须购买主件，才能购买该附件。求在购买总费用内，能购买多少物品，使得所有物品的价格*重要度的总和最大。数据结构 本题与经典动态规划本题与经典动态规划0101背包问题十分类似。但不同点是，对于每个背包问题十分类似。但不同点是，对于每个附件，必须先购买主件。所以，考虑把附件和主件捆绑在一起考虑。设附件，必须先购买主件。所以，考虑把附件和主件捆绑在一起考虑。设 物品物品i i的价格为的价格为titi、重

21、要度为、重要度为pipi；FiFi表示使用表示使用i i元可以购买的价格元可以购买的价格* *重要度的最大值。主附件组合的方式有四种，其中第重要度的最大值。主附件组合的方式有四种，其中第i i种组合的单价为种组合的单价为ttitticonst maxt=32000; maxn=60;const maxt=32000; maxn=60;type ftype=array0.maxtof longint;type ftype=array0.maxtof longint;var var f:ftype; fi f:ftype; fi表示使用表示使用i i元可以购买的价格元可以购买的价格* *重要度的最

22、大值重要度的最大值 ff:array1.4of ftype;ffk,j ff:array1.4of ftype;ffk,j为使用为使用j j元且物品元且物品i i采用第采用第k k种组合方式种组合方式可以购买的价格可以购买的价格* *重要度的最大值重要度的最大值 t,p,prt,pp:array1.maxnof longint; t,p,prt,pp:array1.maxnof longint; 物品物品i i的价格为的价格为titi、重要度、重要度为为pipi； prtiprti是附件是附件i i所属的主件序号，所属的主件序号，ppippi为主件为主件i i的附件个数的附件个数 g:arra

23、y1.maxn,1.2of longint;gI,j g:array1.maxn,1.2of longint;gI,j为主件为主件i i的第的第j j个附件的序号个附件的序号 pt,tt:array1.4of longint; pt,tt:array1.4of longint;第第i i种组合的价格为种组合的价格为ttitti；重要度；重要度* *价格价格为为ptipti tott,n, :longint; tott,n, :longint; 总钱数为总钱数为totttott、希望购买的物品数为、希望购买的物品数为n n 分析主附件组合的四种方式主件主件i i没有附件的：没有附件的：pipi*

24、 *titi；tt1=tt1=titi主件主件i i只有一个附件只有一个附件j j：pipi* *ti+pjti+pj* *tjtj，tt2= tt2= ti+tjti+tj主件主件i i有两个附件有两个附件j1j1和和j2j2。有四种组合方式。有四种组合方式仅购买主件仅购买主件i i：pipi* *titi，tt1=tt1=titi购买主件购买主件i i和附件和附件j1j1：pipi* *ti+pj1ti+pj1* *tj1tj1，tt2= ti+tj1tt2= ti+tj1购买主件购买主件i i和附件和附件j2j2：pipi* *ti+pj2ti+pj2* *tj2tj2，tt3= ti+

25、tj2tt3= ti+tj2购买主件购买主件i i、附件、附件j1j1和和j2j2：pipi* *ti+pj1ti+pj1* *tj1+ pj2tj1+ pj2* *tj2tj2，tt4= tt4= ti+tj1+tj2ti+tj1+tj2每一种组合方式为每一种组合方式为1 1个背包，分别使用动态规划解背包问个背包，分别使用动态规划解背包问题。题。动态规划阶段阶段i i：依次按照物品数递增的顺序考虑前：依次按照物品数递增的顺序考虑前i i个物品的最优个物品的最优方案。每个阶段需要进行双重动态规划方案。每个阶段需要进行双重动态规划1 1、计算前、计算前i i个物品的所有可能的组合方案个物品的所有

26、可能的组合方案计算物品计算物品i i的组合方案数的组合方案数kkkk；状态状态k k ：枚举每一个组合方案：枚举每一个组合方案k k（1kkk1kkk）决策决策j j ：按照：按照递减顺序递减顺序( (如果是递增顺序呢如果是递增顺序呢?)?)枚举花费枚举花费j j（j=mttkj=mttk）设设ffk,jffk,j为使用为使用j j元且物品元且物品i i采用第采用第k k种组合方式可以购种组合方式可以购买的价格买的价格* *重要度的最大值重要度的最大值 ffk,j= max(ffk,j= max(考虑前考虑前i-1i-1个物件花费个物件花费j-ttkj-ttk的最优的最优值值+ +主件主件i

27、i的第的第k k种组合中价格与重要度乘积的和种组合中价格与重要度乘积的和) )2 2、计算四个背包中的最大值、计算四个背包中的最大值Fj Fj 状态j：按照递减方向枚举所有可能的钱数(j= m0)决策k：枚举组合方案（1kkk） fj= 。在递推了n个物品后的fm即为问题的解。算法复杂度O(MN)。（M表示总费用，N表示物品数）,max41jkffkreadln(tott,n);readln(tott,n);输入总钱数和希望购买的物品数输入总钱数和希望购买的物品数 for i:=1 to n dofor i:=1 to n do begin begin readln(ti,pi,prti);

28、readln(ti,pi,prti);输入物品输入物品i i的价格、重要的价格、重要度和主附件标志度和主附件标志 if prti0 if prti0若物品若物品i i是附件，则所属主件的附件个数是附件，则所属主件的附件个数加加1 1，物品，物品i i进入该主件的附件表进入该主件的附件表 then begin then begin inc(ppprti);gprti,ppprti:=i inc(ppprti);gprti,ppprti:=i； endend； end;forend;for fillchar(f,sizeof(f),0); fillchar(f,sizeof(f),0);状态转移方

29、程初始化状态转移方程初始化 for i:=1 to n dofor i:=1 to n do枚举每一个物品枚举每一个物品 if prti=0if prti=0若物品若物品i i是主件是主件 then begin then begin case ppi of case ppi of 0:begin 0:begin若物品若物品i i没有附件，则设组合标志没有附件，则设组合标志1 1；计算；计算物品物品i i的价格与重要度的乘积，记下物品的价格与重要度的乘积，记下物品i i的重要度的重要度 kk:=1;pt1:=pikk:=1;pt1:=pi* *ti;tt1:=titi;tt1:=ti end;

30、end; 1:begin 1:begin若物品若物品i i有一个附件，则设组合标志有一个附件，则设组合标志2 2 kk:=2; pt1:=pi kk:=2; pt1:=pi* *ti;tt1:=ti;ti;tt1:=ti;计算计算物品物品i i的价格与重要度的乘积，记下物品的价格与重要度的乘积，记下物品i i的重要度的重要度 pt2:=pi pt2:=pi* *ti+pgi,1ti+pgi,1* *tgi,1;tgi,1; tt2:=ti+tgi,1 tt2:=ti+tgi,1计算物品计算物品i i的价格与重的价格与重要度的乘积要度的乘积+ +其附件价格与重要度的乘积，记下物品其附件价格与重要

31、度的乘积，记下物品i i与附与附件的重要度的和件的重要度的和 end; end; 2:begin2:begin若物品若物品i i有两个附件，则设组合标志有两个附件，则设组合标志4 4 kk:=4; kk:=4; pt1:=pi pt1:=pi* *ti;tt1:=ti;ti;tt1:=ti;计算物品计算物品i i的价格与重要度的的价格与重要度的乘积，记下物品乘积，记下物品i i的重要度的重要度 pt2:=pi pt2:=pi* *ti+pgi,1ti+pgi,1* *tgi,1;tgi,1; tt2:=ti+tgi,1; tt2:=ti+tgi,1;计算物品计算物品i i的价格与重要度的乘积的

32、价格与重要度的乘积+ +第第1 1个附件价格与重要度的乘积，记下物品个附件价格与重要度的乘积，记下物品i i与第与第1 1个附件的重要度的个附件的重要度的和和 pt3:=pi pt3:=pi* *ti+pgi,2ti+pgi,2* *tgi,2;tgi,2; tt3:=ti+tgi,2; tt3:=ti+tgi,2; 计算物品计算物品i i的价格与重要度的乘积的价格与重要度的乘积+ +第第2 2个附件价格与重要度的乘积，记下物品个附件价格与重要度的乘积，记下物品i i与第与第2 2个附件的重要度个附件的重要度的和的和 pt4:=pi pt4:=pi* *ti+pgi,1ti+pgi,1* *t

33、gi,1+pgi,2tgi,1+pgi,2* *tgi,2;tgi,2; t4:=ti+tgi,1+tgi,2 t4:=ti+tgi,1+tgi,2 计算物品计算物品i i的价格与重要度的价格与重要度的乘积的乘积+ +第第1 1个附件价格与重要度的乘积个附件价格与重要度的乘积+ +第第2 2个附件价格与重要度个附件价格与重要度的乘积，记下物品的乘积，记下物品i i与两个附件的重要度的和与两个附件的重要度的和 end endend;caseend;casefor k:=1 to kk dofor k:=1 to kk do枚举枚举4 4种组合方案种组合方案 beginbegin ffk:=f;

34、ffk:=f;记下前记下前i-1i-1种物品的状态转移方程种物品的状态转移方程 for j:=tott downto ttk do for j:=tott downto ttk do ffkj:=max(ffkj,ffkj- ffkj:=max(ffkj,ffkj-ttk+ptk)ttk+ptk)按照递减方向枚举第按照递减方向枚举第k k种组合方案下所有种组合方案下所有可能的钱数，计算该条件下物品价格与重要度乘积的最大可能的钱数，计算该条件下物品价格与重要度乘积的最大总和总和 end;forend;forfor j:=tott downto 0 dofor j:=tott downto 0 d

35、o按照递减方向枚举所有可能的按照递减方向枚举所有可能的钱数，在所有的组合方案中寻找物品价格与重要度乘积的钱数，在所有的组合方案中寻找物品价格与重要度乘积的最大总和最大总和 for k:=1 to kk do fj:=max(fj,ffkj) for k:=1 to kk do fj:=max(fj,ffkj)end;thenend;thenwriteln(ftott);writeln(ftott);不超过总钱数不超过总钱数totttott的物品价格与重要的物品价格与重要度乘积的最大总和为问题解度乘积的最大总和为问题解 怎样对多个并行的、可划分阶段的进程怎样对多个并行的、可划分阶段的进程进行最优

36、化决策，关键是如何存储状态。进行最优化决策，关键是如何存储状态。多进程问题的状态数目十分庞大，每一个多进程问题的状态数目十分庞大，每一个状态的存储量大，且又是求多条最佳路径，状态的存储量大，且又是求多条最佳路径，这就要求在存储上必须做一定的优化后才这就要求在存储上必须做一定的优化后才有可能实现算法的程序化。主要的优化就有可能实现算法的程序化。主要的优化就是：舍弃一切不必要的存储量。是：舍弃一切不必要的存储量。四、多进程的最优化决策问题例题6 方格取数 设有设有n n* *n n的方格图（的方格图（），我们将其中的某些方格中填入正整数，而其他的方），我们将其中的某些方格中填入正整数，而其他的方格

37、中则放入数字。如下图所示（见样例）：格中则放入数字。如下图所示（见样例）： 某人从图的左上角的点出发，可以向下行走，也可以向右走，直到到达右下角某人从图的左上角的点出发，可以向下行走，也可以向右走，直到到达右下角的点。在走过的路上，它可以取走方格中的数（取走后的方格中将变为数字的点。在走过的路上，它可以取走方格中的数（取走后的方格中将变为数字）。此人从点到点共走两次，试找出条这样的路径，使得取得的数之和）。此人从点到点共走两次，试找出条这样的路径，使得取得的数之和最大。最大。输入：输入的第一行为一个整数（表示的方格图），接下来的每行右三个整输入：输入的第一行为一个整数（表示的方格图），接下来的

38、每行右三个整数，前两个表示位置，第三个数为该位置上所放的数。一行单独的表示输入结数，前两个表示位置，第三个数为该位置上所放的数。一行单独的表示输入结束。束。输出：只需输出一个整数，表示条路径上取得的最大的和输出：只需输出一个整数，表示条路径上取得的最大的和1 1、状态的设计、状态的设计 对于本题来说，状态的选定和存储对整个问题的处理起了决定性对于本题来说，状态的选定和存储对整个问题的处理起了决定性的作用。的作用。我们从（我们从（1 1，1 1）出发，每走一步作为一个阶段，则可以分成）出发，每走一步作为一个阶段，则可以分成2 2* *n-1n-1个个阶段：阶段： 第一个阶段，两条路径从（第一个阶

39、段，两条路径从（1 1，1 1）出发；）出发； 第二个阶段，两条路径可达（第二个阶段，两条路径可达（2 2，1 1）和（）和（1 1，2 2）；）； 第三个阶段，两条路径可达的位置集合为（第三个阶段，两条路径可达的位置集合为（3 3，1 1）、（）、（2 2，2 2）和）和（1 1，3 3）；）； 第第2 2* *n-1n-1个阶段，两条路径汇聚（个阶段，两条路径汇聚（n n，n n）；）；在第在第k(1k2k(1k2* *n-1)n-1)个阶段，两条路径的终端坐标（个阶段，两条路径的终端坐标（x x1 1，y y1 1）（）（x x2 2，y y2 2）位于对应的右下对角线上。如下图所示：位

40、于对应的右下对角线上。如下图所示： 1 1、状态的设计、状态的设计 如果我们将两条路径走第如果我们将两条路径走第i i步的所有可能位置定义为当前阶段的步的所有可能位置定义为当前阶段的状态的话，面对的问题就是如何存储状态了。方格取数问题的状状态的话，面对的问题就是如何存储状态了。方格取数问题的状态数目十分庞大，每一个位置是两维的，且又是求两条最佳路径，态数目十分庞大，每一个位置是两维的，且又是求两条最佳路径，这就要求在存储上必须做一定的优化后才有可能实现算法的程序这就要求在存储上必须做一定的优化后才有可能实现算法的程序化。主要的优化就是：舍弃一切不必要的存储量。为此，我们取化。主要的优化就是：舍

41、弃一切不必要的存储量。为此，我们取位置中的位置中的x x坐标（坐标（x x1 1，x x2 2）作状态，其中）作状态，其中（1x1x1 1kk）andand（x x1 11n1n）andand（1x1x2 2kk）andand（x x2 21n1n）直接由直接由x x坐标计算对应的坐标计算对应的y y坐标：坐标：（y y1 1=k+1-x=k+1-x1 1）andand（y y1 11n1n）andand（y y2 2=k+1-x=k+1-x2 2）andand（y y2 21n 1n 2 2、状态转移方程、状态转移方程 设两条路径在设两条路径在k k阶段的状态为（阶段的状态为（x x1 1，

42、x x2 2）。由（）。由（y y1 1=k+1-x=k+1-x1 1）（y y1 11.n1.n）得出第一条路径的坐标为（）得出第一条路径的坐标为（x x1 1，y y1 1）；由（）；由（y y2 2=k+1-x=k+1-x2 2）（y y2 21.n1.n）得出第二条路径的坐标为（）得出第二条路径的坐标为（x x2 2，y y2 2）。）。 假设在假设在k-1k-1阶段，两条路径的状态为（阶段，两条路径的状态为（x x1 1，x x2 2）且（）且（x x1 1，x x2 2）位于（位于（x x1 1，x x2 2）状态的左邻或下邻位置。因此我们设两条路径的延）状态的左邻或下邻位置。因此

43、我们设两条路径的延伸方向为伸方向为d d1 1和和d d2 2：d di i=0=0，表明第，表明第i i条路径由（条路径由（x xi i，y yi i）向右延伸至）向右延伸至（x xi i，y yi i）；）；d di i=1=1，表明第，表明第i i条路径由（条路径由（x xi i，y yi i）向下延伸至（）向下延伸至（x xi i，y yi i）（）（1i21i2）。）。 显然（显然（x x1 1= x= x2 2）（d d1 1= d= d2 2），表明两条路径重合，同时取走），表明两条路径重合，同时取走了（了（x x1 1，y y1 1）和（）和（x x1 1，y y1 1）中的数

44、，这种取法当然不可能得到最）中的数，这种取法当然不可能得到最大数和的。大数和的。2 2、状态转移方程、状态转移方程分析两种可能：分析两种可能：若若x x1 1=x=x2 2，则两条路径会合于，则两条路径会合于x x1 1状态，可取走（状态，可取走（x x1 1，y y1 1）中的数）中的数( (如如下图下图) )； x x1 1(x(x2 2)x)x1 1=x=x2 2 x x2 2(x(x1 1)若若x x1 1xx2 2，则在，则在k k阶段，第一条路径由阶段，第一条路径由x x1 1状态延伸至状态延伸至x x1 1状态，第状态，第二条路径由二条路径由x x2 2状态延伸至状态延伸至x x

45、2 2状态，两条路径可分别取走（状态，两条路径可分别取走（x x1 1，y y1 1）和（和（x x2 2，y y2 2）中的数）中的数( (如下图如下图) )；设设 fkfk，x x1 1，x x2 2在第在第k k阶段，两条路径分别行至阶段，两条路径分别行至x x1 1状态和状态和x x2 2状态的状态的最大数和。显然最大数和。显然k=1k=1时，时，f1f1，1 1，1=01=0；k2k2时，时，fkfk，x x1 1，x x2 2=maxfk-1=maxfk-1， x x1 1，x x2 2+(x+(x1 1，y y1 1) )的数字的数字xx1 1=x=x2 2，fk-1fk-1，

46、x x1 1，x x2 2+(x+(x1 1，y y1 1) )的数字的数字+(x+(x2 2，y y2 2) )的数字的数字xx1 1xx2 2 1k2 1k2* *n-1n-1，x x1 1可达可达x x1 1的状态集合，的状态集合，x x2 2可达可达x x2 2的状态集合，的状态集合，（x x1 1xx2 2）(d d1 1dd2 2) )； 由于第由于第k k个阶段的状态转移方程仅与第个阶段的状态转移方程仅与第k-1k-1个阶段的状态发生个阶段的状态发生联系，因此不妨设联系，因此不妨设 f f0 0第第k-1k-1个阶段的状态转移方程；个阶段的状态转移方程； f f1 1第第k k个

47、阶段的状态转移方程；个阶段的状态转移方程；初始时，初始时，f f0 011，1=01=0。经过。经过2 2* *n-1n-1个阶段后得出的个阶段后得出的f f0 0nn，nn即为问题即为问题的解。的解。3 3、多进程决策的动态规划、多进程决策的动态规划 由于方格取数问题是对两条路径进行最优化决策的，因此称这类由于方格取数问题是对两条路径进行最优化决策的，因此称这类动态规划为动态规划为分阶段、多进程分阶段、多进程的最优化决策过程。设的最优化决策过程。设阶段阶段i i：准备走第：准备走第i i步（步（1i21i2* *n-1n-1）；）；状态（状态（x x1 1，x x2 2）：）： 第第i-1i

48、-1步的状态号（步的状态号（1x1x1 1，x x2 2i-1i-1。x x1 1，x x2 21.n1.n）决策（决策（d d1 1，d d2 2）：第一条路径由）：第一条路径由x x1 1状态出发沿状态出发沿d d1 1方向延伸、第二方向延伸、第二条路径由条路径由x x2 2状态状态 出发沿出发沿d d2 2方向延伸，可使得两条路径的数和方向延伸，可使得两条路径的数和最大（最大（0d0d1 1，d d2 211。方向。方向0 0表示右移，方向表示右移，方向1 1表示下移）；表示下移）；fillchar(f0fillchar(f0，sizeof(f0)sizeof(f0)，0) 0)； 行走

49、前的状态转行走前的状态转移方程初始化移方程初始化 f01f01，1010；for i2 to n+n-1 dofor i2 to n+n-1 do阶段：准备走第阶段：准备走第i i步步 begin begin fillchar(f1 fillchar(f1，sizeof(f1)sizeof(f1)，0) 0)； 走第走第i i步的状态步的状态转移方程初始化转移方程初始化 for x for x1 11 to i-1 do1 to i-1 do枚举两条路径在第枚举两条路径在第i-1i-1步时的状态步时的状态x x1 1和和x x2 2 for x for x2 21 to i-1 do1 to

50、i-1 do begin begin 计算计算y y1 1和和y y2 2； if (xif (x1 1，y y1 1)和和(x (x2 2，y y2 2)在界内在界内 thenthen for d for d1 10 to 1 do 0 to 1 do 决策：计算两条路径的最决策：计算两条路径的最佳延伸方向佳延伸方向 for d for d2 20 to 1 do 0 to 1 do beginbegin 第第1 1条路径沿条路径沿d d1 1方向延伸至方向延伸至(x (x1 1，y y1 1）；）； 第第2 2条路径沿条路径沿d d2 2方向延伸至方向延伸至(x (x2 2，y y2 2)

51、 )； i f ( ( xi f ( ( x1 1， y y1 1) ) 和和 ( x( x2 2， y y2 2) ) 在 界在 界内内)(d)(d1 1dd2 2)(x)(x1 1xx2 2) ) 计算第计算第i i步的状态步的状态转移方程转移方程 then f1x then f1x1 1，x x2 2maxf0 xmaxf0 x1 1，x x2 2+mapx+mapx1 1，y y1 1xx1 1=x=x2 2，f0 xf0 x1 1，x x2 2+mapx+mapx1 1，y y1 1+mapx+mapx2 2，y y2 2xx1 1xx2 2 end end；forfor end e

52、nd；for for f0f1 f0f1； 记下第记下第i i步的状态转移方程步的状态转移方程 endend；forfor输出两条路径取得的最大数和输出两条路径取得的最大数和f0nf0n，n n例题13 过河【输入文件】输入文件【输入文件】输入文件river.inriver.in的第一行有一个正整数的第一行有一个正整数L L（1 L 1 L 10109 9），表示独木桥的长度。第二行有三个正整数），表示独木桥的长度。第二行有三个正整数S S，T T，MM，分别表，分别表示青蛙一次跳跃的最小距离，最大距离，及桥上石子的个数，其中示青蛙一次跳跃的最小距离，最大距离，及桥上石子的个数，其中1ST10

53、1ST10，1M 1001M 100。第三行有。第三行有MM个不同的正整数分别表示这个不同的正整数分别表示这MM个石子在数轴上的位置（数据保证桥的起点和终点处没有石子）。个石子在数轴上的位置（数据保证桥的起点和终点处没有石子）。所有相邻的整数之间用一个空格隔开。所有相邻的整数之间用一个空格隔开。【输出文件】输出文件【输出文件】输出文件river.outriver.out只包括一个整数，表示青蛙过河最少需只包括一个整数，表示青蛙过河最少需要踩到的石子数。要踩到的石子数。方法2、动态规划 1、以桥为规划对象、以桥为规划对象 设optn为青蛙到达n位置最少需要踩到的石子数。 rockn= 位置无石子

54、位置有石子nn01minnrockinoptnoptTiS这个方程的时间复杂度是O（n）级的 ，显然在竞赛时限内， n109的极限数据是无法出解的 2、以石子为规划对象、以石子为规划对象 相比上限为109的桥长L而言，石子数M要小得多，因为其上限充其量为100。我们以石子为对象，由左而右地进行规划。设 xi为桥上由左而右顺序的第i个石子位置；ai,j为青蛙跳至xi左方相对距离为j的位置时所经过的最少石子总数（0in，0jt-1）。若j=0，说明青蛙踩到了桥上的第i个石子。初始时，ai,j=n+1。显然，青蛙在跳跃过程中有两种可能：第1种情况：xi-j位置位于xi-1的左方，即xi-jxi-1

55、显然，跳至xi-j位置经过的最少石子总数为ai-1,j-xi+xi-1第2种情况：xi-j位置位于xi-1的右方，即xi-jxi-1 显然，如果青蛙能够由xi-1-v位置跳至xi-j位置，则跳至xi-j位置经过的石子总数为ai-1,v或者为ai-1,v+1（j=0时，即踩到了桥上的第i个石子）。但究竟v多大时，才能使得最少石子数最少呢，我们无法预知，只能在0t-1的范围内一一枚举v，从中找出经过的最少石子数。 ai,j=最后，我们枚举青蛙跳出独木桥前的最后一个起跳位置最后，我们枚举青蛙跳出独木桥前的最后一个起跳位置xn-xn-i(0it-1i(0it-1），从中计算出青蛙过河最少需要踩到的石子

56、数），从中计算出青蛙过河最少需要踩到的石子数现在动态规划的关键变成了如何判断青蛙能否从现在动态规划的关键变成了如何判断青蛙能否从xi-1-vxi-1-v位置跳至位置跳至xi-jxi-j位置，即青蛙能否跳到相对距离为位置，即青蛙能否跳到相对距离为v v远的位置。远的位置。 ,min10inati状态转移方程状态转移方程0,11 1, 1min0,1 1, 1min 11, 11010jixjixjixvixviajixjixjixvixviaixjixixixjiatvtv位置位置跳至青蛙能够从位置位置跳至青蛙能够从如果相对距离vs(s-1)的话，青蛙是一定能够跳到的如果相对距离vs(s-1)，

57、则用一次跳跃的距离范围递推设n为桥上的石子数（1nm）；bi为能否用s到t的一次跳跃距离跳至i远的标志bi=true i=0bi= 1i90cv为青蛙能否跳到相对距离为v远的标志（v90） cv= jibortjs) 1(0) 1(0ssvvbssvtruevfalse解决一个特例 当S=T时上述等式是无法使用的，因为在这种情况下，青蛙不可避免地跳到其位置为S倍数的石子上，因此只需要在所有石子中，统计出坐标是S倍数的石子个数就可以了。 var L,s,t,m,n,i,j,v,best:longint; x:array 0.100 of longint;由左而右记录每个石子的位置由左而右记录每个石子的位置 a:array 0.100,0.9 of longint;ai,j为青蛙跳到为青蛙跳到xi-j位置经过的位置经过的最少石子数最少石子数 b:array -10.90 of boolean;bi记录能否用记录能否用s到到t这