动态规划(动态程序设计)课件.ppt

动态规划动态规划上海市控江中学上海市控江中学 王建德王建德讨论的问题讨论的问题1 1、动态规划的基本概念、动态规划的基本概念2 2、动态规划的基础题型、动态规划的基础题型3 3、动态规划的综合题型、动态规划的综合题型 基本概念基本概念动态程序设计是解决多阶段决策最优化问动态程序设计是解决多阶段决策最优化问题的一种思想方法。所谓题的一种思想方法。所谓“动态动态”，指的，指的是在问题的多阶段决策中，按某一顺序，是在问题的多阶段决策中，按某一顺序，根据每一步所选决策的不同，将随即引起根据每一步所选决策的不同，将随即引起状态的转移，最终在变化的状态中产生一状态的转移，最终在变化的状态中产生一个决策序列。动态规划就是为了使产生的个决策序列。动态规划就是为了使产生的决策序列在符合某种条件下达到最优。决策序列在符合某种条件下达到最优。DAGCKBNPOMJFHELI312345214323142212223344阶段阶段1阶段阶段2阶段阶段3阶段阶段4阶段阶段5问题的引出：问题的引出：P P是出发点，从是出发点，从P P到到A A，求最短路径求最短路径思路令 从从P A的最短路径为的最短路径为P(A)；P(A)=minP(B)+2,P(C)+3；从从P B的最短路径为的最短路径为P(B)；P(B)=minP(D)+1,P(E)+2；从从P C的最短路径为的最短路径为P(C);P(C)=minP(E)+5,P(F)+4；上述递推公式告诉我们，要求上述递推公式告诉我们，要求P(A)P(A)需要先求出阶段需要先求出阶段5 5中的中的P(B)P(B)和和P(C)P(C)；要求要求 P(B)(P(B)(或者或者P(C)P(C)），），又要先求出阶段又要先求出阶段4 4中的中的 P(D)P(D)和和 P(E)(P(E)(或或P(F)P(F)和和P(E)P(E)（倒推）（倒推）显然，要依照上述递推过程求解，需要倒过来，从显然，要依照上述递推过程求解，需要倒过来，从P(P)P(P)出发，先求出第一阶段的出发，先求出第一阶段的P(O)P(O)和和P(N)P(N)，再求第二阶段的再求第二阶段的P(K)P(K)，P(L)P(L)，P(M)P(M)；，最后得到最后得到P(A)P(A)（顺推）。（顺推）。h30h31h32h20h21h22h10h11h12h00h01h02v20v21v22v23v10v11v12v13v00v01v02v03(3,3)0213213yx数据结构数据结构将每条路经的长度存在数组中东西方向上的道路长度存将每条路经的长度存在数组中东西方向上的道路长度存在两维数组在两维数组h43h43中中,规定数组的第一维为行号，第二规定数组的第一维为行号，第二维为列号。维为列号。h43=3,2,3,2,1,4,3,4,5,3,1,2;南北方向上道路长度存至数组南北方向上道路长度存至数组v34v34中，也规定中，也规定第一维为行号，第二维为列号。第一维为行号，第二维为列号。v34=2,2,3,4,4,1,2,4,1,2,2,3;求解过程为从(0,0)到(3,3)求最短路径问题定义二维数组，P44=0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,第一维为行，第二维为列。这时P(O)为P01；P(N)为P10；P(A)为P33，以下为分阶段递推求解过程。P00=0;阶段阶段1:P01=P00+h00=0+3=3;P10=P00+v00=0+2=3;阶段阶段2:P11=min P01+v01,P10+h10=min3+1,2+2=4 P02=P01+h10=3+2=5;P20=P10+v10=2+4=6 阶段阶段3:P12=min P02+v02,P11+h11=min5+3,4+1=5 P03=P02+h02=5+3=8;P30=P20+v20=6+1=7 P21=min P11+v11,P20+h20=min4+1,6+1=5阶段阶段4:P13=min P03+v03,P12+h12=min8+4,5+4=9 P22=min P12+v12,P21+h21=min5+2,5+4=7 P31=min P21+v21,P30+h30=min5+2,7+3=7 阶段阶段5:P23=min P13+v13,P22+h22=min9+4,7+5=12 P32=min P22+v22,P31+h31=min7+2,7+1=8最后最后:P33=min P23+v23,P32+h32=min/*12+3,8+2=10综上，数组综上，数组P P的通项表示为的通项表示为Pij=min(pi-1j+vi-1j),(pij-1+hij-1)Pij=min(pi-1j+vi-1j),(pij-1+hij-1)(i,j0)(i,j0)P0j=P0j-1+h0j-1P0j=P0j-1+h0j-1(i=0,j0)(i=0,j0)Pi0=Pi-10+vi-10Pi0=Pi-10+vi-10(i0,j=0)(i0,j=0)P P数组数据数组数据圆圈内为路口对圆圈内为路口对P P点的最小距点的最小距离离,箭头为最佳行走路径。箭头为最佳行走路径。for j 1 to 4 do /*计算计算0行上的每点的距离行上的每点的距离*/p0j p0j-1+h0j-1;For i 1 to 4 do /*计算计算0列上的每点的距离列上的每点的距离*/pi0 pi-10+vi-10;for i 1 to 4 do for j 1 to 4 do pijmin(pi-1j+vi-1j),(pij-1+hij-1);For i3 downto 0 do /*输出每个路口对输出每个路口对P点的最小距离点的最小距离*/for j 0 to 3 do write(pij:4)writeln;/*for*/程序程序 阶段：据空间顺序或时间顺序对问题的求解划分阶段。阶段：据空间顺序或时间顺序对问题的求解划分阶段。状态：描述事物的性质，不同事物有不同的性质，因状态：描述事物的性质，不同事物有不同的性质，因而用不同的状态来刻画。对问题的求解状态的描述是分而用不同的状态来刻画。对问题的求解状态的描述是分阶段的。阶段的。决策：根据题意要求，对每个阶段所做出的某种选择决策：根据题意要求，对每个阶段所做出的某种选择性操作。性操作。状态转移方程：用数学公式描述与阶段相关的状态间状态转移方程：用数学公式描述与阶段相关的状态间的演变规律。的演变规律。多阶段决策过程：将所研究的过程划分为若干个相互多阶段决策过程：将所研究的过程划分为若干个相互联系的阶段，在求解时，对每一个阶段都要做出决策，联系的阶段，在求解时，对每一个阶段都要做出决策，前一个决策确定以后，常常会影响下一个阶段的决策。前一个决策确定以后，常常会影响下一个阶段的决策。动态规划的几个要素动态规划的几个要素 “最优性原理最优性原理”：不论初始状态和第一步：不论初始状态和第一步决策是什么，余下的决策相对于前一次决策所决策是什么，余下的决策相对于前一次决策所产生的新状态，构成一个最优决策序列。产生的新状态，构成一个最优决策序列。最优决策序列的子序列，一定是局部最优决最优决策序列的子序列，一定是局部最优决策子序列。注意包含有非局部最优的决策子序策子序列。注意包含有非局部最优的决策子序列，一定不是最优决策序列列，一定不是最优决策序列,例如贪心法。例如贪心法。动态规划的依据动态规划的依据“最优性原理最优性原理”动态规划的指导思想动态规划的指导思想在做每一步决策时，列出各种可能的局部解，之后在做每一步决策时，列出各种可能的局部解，之后依据某种判定条件，舍弃那些肯定不能得到最优解依据某种判定条件，舍弃那些肯定不能得到最优解的局部解。这样，在每一步都经过筛选，以每一步的局部解。这样，在每一步都经过筛选，以每一步都是最优的来保证全局是最优的。筛选相当于最大都是最优的来保证全局是最优的。筛选相当于最大限度地有效剪枝（从搜索角度看），效率会十分高。限度地有效剪枝（从搜索角度看），效率会十分高。但它又不同于贪心法。但它又不同于贪心法。贪心法贪心法:产生一个按贪心策略形成的判定序列，该产生一个按贪心策略形成的判定序列，该序列不保证解是全局最优的，因为有些问题不符合序列不保证解是全局最优的，因为有些问题不符合最优性原理。最优性原理。动态规划动态规划:产生许多判定序列，再按最优性原理对产生许多判定序列，再按最优性原理对这些序列加以筛选，去除那些非局部最优的子序列这些序列加以筛选，去除那些非局部最优的子序列。2 2、动态规划的基础题型、动态规划的基础题型1 1、路径问题、路径问题2 2、0101背包问题背包问题3 3、求最佳子序列问题、求最佳子序列问题4 4、双重动态规划、双重动态规划路径问题的讨论路径问题的讨论问题的一般形式：问题的一般形式：1 1、计算所有路径方案、计算所有路径方案 2 2、计算一条最佳路径、计算一条最佳路径 3 3、计算两条最佳路径（多进程的最优化决策）、计算两条最佳路径（多进程的最优化决策）一般方法：一般方法：按照出发点走出的步数划分阶段，将当前步可达按照出发点走出的步数划分阶段，将当前步可达的顶点集定义为状态，当前步如何走定义为决策。的顶点集定义为状态，当前步如何走定义为决策。注意：注意：1 1、可能需要将原题转化为路径问题、可能需要将原题转化为路径问题 2 2、如果最佳路径问题不满足最优子结构特征特、如果最佳路径问题不满足最优子结构特征特征的话，可以转化为判定性问题求解。征的话，可以转化为判定性问题求解。一、计算所有方案一、计算所有方案 对于一些阶段性强、但不属于最优化的问题，是对于一些阶段性强、但不属于最优化的问题，是否也可以借助动态规划方法呢？如果我们可以找出否也可以借助动态规划方法呢？如果我们可以找出状态转移的关系，并在状态转移方程状态转移的关系，并在状态转移方程中去掉最佳性要求中去掉最佳性要求optopt（minmin或或maxmax），将扩展子状），将扩展子状态的所有行动作为决策，则可以例举出由初始状态的所有行动作为决策，则可以例举出由初始状态至目标状态的所有方案。显然，在计数类问题态至目标状态的所有方案。显然，在计数类问题中使用这种方法要比回溯法等搜索算法简捷许多。中使用这种方法要比回溯法等搜索算法简捷许多。例题 过河卒 如如图图，A A点点有有一一个个过过河河卒卒，需需要要走走到到目目标标B B点。卒行走的规则：可以向下、或者向右。点。卒行走的规则：可以向下、或者向右。同同时时在在棋棋盘盘上上的的任任一一点点有有一一个个对对方方的的马马（如如上上图图的的C C点点）,该该马马所所在在的的点点和和所所有有跳跳跃跃一一步步可可达达的的点点称称为为对对方方马马的的控控制制点点。例例如如上上图图C C点点上上的的马马可可以以控控制制8 8个个点点（图图中中的的P1P1，P2P2.P8.P8）。卒卒不不能能通通过过对对方方马的控制点。马的控制点。棋棋盘盘用用坐坐标标表表示示，A A点点（0 0，0 0）、B B点点（n n，m m）(n,m(n,m为为不不超超过过2020的的整整数数,并并由由键键盘盘输输入入)，同同样样马马的的位位置置坐坐标标是是需需要要给给出出的的（约约定定：CACA，同同时时CBCB）。现现在在要要求求你你计计算算出出卒卒从从A A 点点能能够够到到达达B B点点的路径的条数。的路径的条数。输输 入入：键键盘盘输输入入B B点点的的坐坐标标(n,m)(n,m)以以及及对对方方马马的的坐坐标标（X X，Y Y）输输 出：屏幕输出一个整数（路径的条数）。出：屏幕输出一个整数（路径的条数）。按照题意，对方的马所在的点和所有跳跃一步可达的点称为对方马的控制点，卒不能通过对方马的控制点。在卒出发之前，必须计算对方马的所有控制点。显然，若（0，0）或（n,m）为控制点，则输出路径数为0。设constconstmove:array1.8,1.2of move:array1.8,1.2of integer integer /*/*movekmovek，1.21.2为马沿为马沿k k方向跳跃一步的水平增量和垂直增量方向跳跃一步的水平增量和垂直增量*/=(1,-2),(1,2),(2,1),(2,-1),(-1,2),(-=(1,-2),(1,2),(2,1),(2,-1),(-1,2),(-1,-2),(-2,1),(-2,-1)1,-2),(-2,1),(-2,-1)；varvar list:array-1.20,-1.20of list:array-1.20,-1.20of compcomp；/*/*listi,jlisti,j 为卒从为卒从(0,0)(0,0)到到(i,j)(i,j)的路径数的路径数*/can:array0.20,0.20of can:array0.20,0.20of booleanboolean；/*/*cani,jcani,j 为允许卒通行为允许卒通行(i,ji,j)的标志的标志*/1 1、计算对方马的控制点、计算对方马的控制点设马的初始位置为（设马的初始位置为（x,yx,y）。按照下述方）。按照下述方式计算式计算cancan序列序列canx,y false；/*对方马所在的点为控制点对方马所在的点为控制点*/for i1 to 8 do /*从（从（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,kfalse；/*for*/if(not can0,0)or(not cann,m)/*若若卒卒的的起起点点和和终终点点为为控制点，则输出路径数控制点，则输出路径数0*/then writeln(0)else计计算算和和输输出出卒卒从从（0，0）走走到到（n,m）点点的的路路径径数数listn,m；/*else*/我我们们按按照照由由上上而而下下、由由左左而而右右的的顺顺序序，将将卒卒可可能能到到达达的的每每一一个位置个位置（i,ji,j）(0in(0in，0jm)0jm)设为阶段和状态。设为阶段和状态。首首先先，将将卒卒的的出出发发点点（0 0，0 0）的的路路径径数数设设为为1 1，该该位位置置设设为为控控制制点点（list0,01;can0,0 list0,01;can0,0 falsfals）。然然后后从从（0 0，0 0）出出发发，按按照照由由上上而而下下、由由左左而而右右的的顺顺序序计计算算卒卒经经过过每每一一个个可可行行点点的的路路径径数数:若若（i i，j j）为为可可行行点点，则则走走前前位位置置（i-1,ji-1,j）和和（i,j-1i,j-1）的的路路径数加起来，即为从（径数加起来，即为从（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即为问题的解。由此得出算法：即为问题的解。由此得出算法：fillchar(list,sizeof(list),0)；/*路路径径数数序序列列初初始始化化*/list0,01；can0,0 false；/*卒卒从从（0，0）出出发发的的路路径数为径数为1，该位置不再允许卒通行，该位置不再允许卒通行*/for i0 to n do /*按按照照由由上上而而下下、由由左左而而右右计计算从算从(0,0)到每个可行点的路径数到每个可行点的路径数*/for j0 to m do if cani,jthen listi,jlisti-1,j+listi,j-1；输出卒从（输出卒从（0，0）走到（）走到（n,m）点的路径条数点的路径条数listn,m；2 2、计算和输出卒从（、计算和输出卒从（0 0，0 0）走到（）走到（n,mn,m）点的路径条数）点的路径条数计算一条最佳路径计算一条最佳路径以路径长度划分阶段，从出发点走以路径长度划分阶段，从出发点走i i步可达的顶点集合为状态。步可达的顶点集合为状态。设设fi,jfi,j 为到达阶段为到达阶段i i的顶点的顶点j j的最优解。的最优解。枚举第枚举第i-1i-1阶段中与状态阶段中与状态j j相连的状态相连的状态k,k,其子问题的最优解其子问题的最优解 fi-1,k+fi-1,k+状态状态k k至状态至状态j j的决策代价的决策代价w wk,jk,j即为阶段即为阶段i i的状态的状态j j的的一种方案。枚举了所有可能方案后即可得出一种方案。枚举了所有可能方案后即可得出fi,jfi,j。fi-1,k1Wk1,jfi-1,k2Wk2,jfi-1,kpWkp,j寻宝游戏寻宝游戏 分析分析在“藏宝图”中寻求一条含len个顶点的路径，使得(1klen)(xk,yk)-ak)2最小。数据结构数据结构const ex:array1.4of shortint=(0,0,1,-1);ey:array1.4of shortint=(1,-1,0,0);var n,m,len,i,j,k,l,i0,j0:integer;/*n,m为为“藏宝图藏宝图”的规模的规模*/mp:array1.50,1.50of integer;/*“藏宝图藏宝图”*/c0,c1:array1.50,1.50of longint;/*c0I,j为为ck-1,I,j;c1I,j为为ck,I,j*/a:array1.150of integer;/*数列数列*/ans:longint;/*数列与表格的接近程度数列与表格的接近程度*/输入信息，计算c0的初始值readln(f,n,m);/*输入输入“藏宝图藏宝图”的规模的规模*/for i1 to n do /*输入输入“藏宝图藏宝图”*/for j1 to m do read(f,mpi,j);readln(f,len);/*输入数列的项数输入数列的项数len*/for i1 to len do read(f,ai);/*输入数列输入数列*/for i1 to n do /*计算初始解计算初始解*/for j1 to m do c0i,jsqr(a1-mpi,j);for k2 to len do /*阶段阶段:路径长度路径长度*/for i1 to n do /*状态状态:当前位置当前位置*/for j1 to m do c1i,jmaxint;for l1 to 4 do /*决策决策:选择最佳移前位置选择最佳移前位置*/i0i+exl;j0j+eyl;if(i0 in 1.n)and(j0 in 1.m)and(c0i0,j0c1i,j)then c1i,jc0i0,j0 ;/*for*/c1i,jc1i,j+sqr(mpi,j-ak);/*for*/c0c1;/*for*/ansmaxint;/*计算计算ansminc1I,j*/for i1 to n do for j1 to m do if c1i,j=0)and(aj+xaj+y)then aj+xaj+y;/*for*/ans -1;/*在在t时间内采到草药的最大总价值时间内采到草药的最大总价值ans=*/for i 0 to t do if ansai then ans ai;writeln(ans);/*输出输出t时间内可采到的草药的最大总价值时间内可采到的草药的最大总价值*/.Chain 拜特兰并不总是一个非常民主的国家，也有一些阴暗的历史。一个拜特兰并不总是一个非常民主的国家，也有一些阴暗的历史。一个美好的日子，拜特将军该国的统帅作了一个用以结束长期内战的美好的日子，拜特将军该国的统帅作了一个用以结束长期内战的决定，释放被关押的反对派。然而，他并未让反对派的领袖拜特萨决定，释放被关押的反对派。然而，他并未让反对派的领袖拜特萨直接自由，而是用一根直接自由，而是用一根“拜特链拜特链”将拜特萨锁在墙边将拜特萨锁在墙边.该链子由很多该链子由很多环和固定在墙上栅栏组成。尽管环并未和栅栏融合在一起，但想除环和固定在墙上栅栏组成。尽管环并未和栅栏融合在一起，但想除去它们却非常困难。去它们却非常困难。“将军，你为什么要用链子将我锁在墙边而不让我自由！将军，你为什么要用链子将我锁在墙边而不让我自由！”拜特拜特萨大叫道。萨大叫道。“拜特萨，你并未完全被链子锁住，我可以坦率的告诉拜特萨，你并未完全被链子锁住，我可以坦率的告诉你，你完全可以从栅栏上解下环。你，你完全可以从栅栏上解下环。”拜特将军不忠地回答，同时他拜特将军不忠地回答，同时他补充说，补充说，“但是，你必须在夜里工作，一个小时之内完成，不能弄但是，你必须在夜里工作，一个小时之内完成，不能弄出任何声音，否则，我将按有关法律制罪。出任何声音，否则，我将按有关法律制罪。”。为了帮助拜特萨！。为了帮助拜特萨！链子上的环按整数链子上的环按整数1,2,n1,2,n进行了编号。我们可以按照以下规则解进行了编号。我们可以按照以下规则解开环：开环：只有一个环时可以被连接到栅栏或从栅栏上拆开。只有一个环时可以被连接到栅栏或从栅栏上拆开。第第1 1号环总能进行连接或拆开号环总能进行连接或拆开 如果如果1,.,k-1(1=kn)1,.,k-1(1=kn)环都被拆开，第环都被拆开，第k k个环被连接时个环被连接时,此此时我们能连接或拆开第时我们能连接或拆开第k+1k+1个环个环.写一个程序：文本文件写一个程序：文本文件LAN.INLAN.IN描述了拜特链的构成描述了拜特链的构成,计算拆除拜特链上全部环的最少操作次数计算拆除拜特链上全部环的最少操作次数,将结果将结果写入文本文件写入文本文件LAN.OUT.LAN.OUT.输入：在文本文件输入：在文本文件LAN.IN LAN.IN 中的第中的第1 1行有一个整数行有一个整数n,1=n=1000.n,1=nm then break;/*计算最后一行的计算最后一行的起始单词序号起始单词序号cn*/cni;inc(cn);if cnn/*若单词若单词n的长度超过的长度超过m，失败退出，失败退出*/then writeln(f0,Print is impossible.);continue;if cn=1/*若若n个单词的长度不足一行，则输出结果个单词的长度不足一行，则输出结果*/then writeln(f0,0);writeln(f0,Line 1:,n);continue;/*then*/动态程序设计动态程序设计ansmaxint;for i1 to n do c0,imaxint;c0,00;for k1 to n-1 do /*递推每一行递推每一行*/for i0 to k-1 do ck,imaxint;/*前前k行的状态转移方程初始化行的状态转移方程初始化*/for ik to n-1 do /*枚举第枚举第k行的尾单词行的尾单词*/ck,imaxint;for ji-1 downto k-1 do /*枚举第枚举第k-1行的尾单词行的尾单词*/if(lgj+1,i=m)and(ck-1,j+(m-lgj+1,i)3ck,i)then ck,ick-1,j+(m-lgj+1,i)3;/*for*/for icn-1 to n-1 do/*记录目前最记录目前最“漂亮值漂亮值”和方案和方案*/if ck,ians then ansck,i;akk;aii/*then*/;/*for*/输出方案输出方案procedure putout(k,i:integer);/*前前k行为前行为前i个单词。输出该方案个单词。输出该方案*/var j:integer;if k=0 then exit;/*递归边界递归边界*/for ji-1 downto k-1 do /*计算第计算第k-1行的尾单词行的尾单词j*/if(lgj+1,i=m)and(ck-1,j+(m-lgj+1,i)3=ck,i)then break;putout(k-1,j);/*递归递归k-1行行*/writeln(f0,Line,k,:,i-j)/*输出输出k行的单词数行的单词数*/;/*putout*/由此得出由此得出writeln(ans);/*输出输出“漂亮漂亮”值值*/putout(ak,ai);/*输出前输出前ak行为前行为前ai个单词的方案个单词的方案*/writeln(f0,Line,ak+1,:,n-ai)/*输出最后一行的单词数输出最后一行的单词数*/一般有两种题型：1、2 2条最佳路径经过顶点的权和最大。条最佳路径经过顶点的权和最大。需要优化状态的存储方式需要优化状态的存储方式 2 2、2 2条最佳路径经过的顶点数最多。条最佳路径经过的顶点数最多。计算计算2 2条最佳路径条最佳路径传纸条传纸条【问题描述问题描述】小渊和小轩是好朋友也是同班同学，他们在一起总小渊和小轩是好朋友也是同班同学，他们在一起总有谈不完的话题。一次素质拓展活动中，班上同学安排做成一个有谈不完的话题。一次素质拓展活动中，班上同学安排做成一个m m行行n n列的矩阵，而小渊和小轩被安排在矩阵对角线的两端，因此，列的矩阵，而小渊和小轩被安排在矩阵对角线的两端，因此，他们就无法直接交谈了。幸运的是，他们可以通过传纸条来进行他们就无法直接交谈了。幸运的是，他们可以通过传纸条来进行交流。纸条要经由许多同学传到对方手里，小渊坐在矩阵的左上交流。纸条要经由许多同学传到对方手里，小渊坐在矩阵的左上角，坐标角，坐标(1,1)(1,1)，小轩坐在矩阵的右下角，坐标，小轩坐在矩阵的右下角，坐标(m,nm,n)。从小渊传。从小渊传到小轩的纸条只可以向下或者向右传递，从小轩传给小渊的纸条到小轩的纸条只可以向下或者向右传递，从小轩传给小渊的纸条只可以向上或者向左传递。在活动进行中，小渊希望给小轩传递只可以向上或者向左传递。在活动进行中，小渊希望给小轩传递一张纸条，同时希望小轩给他回复。班里每个同学都可以帮他们一张纸条，同时希望小轩给他回复。班里每个同学都可以帮他们传递，但只会帮他们一次，也就是说如果此人在小渊递给小轩纸传递，但只会帮他们一次，也就是说如果此人在小渊递给小轩纸条的时候帮忙，那么在小轩递给小渊的时候就不会再帮忙。反之条的时候帮忙，那么在小轩递给小渊的时候就不会再帮忙。反之亦然。亦然。还有一件事情需要注意，全班每个同学愿意帮忙的好感度有还有一件事情需要注意，全班每个同学愿意帮忙的好感度有高有低（注意：小渊和小轩的好心程度没有定义，输入时用高有低（注意：小渊和小轩的好心程度没有定义，输入时用0 0表表示），可以用一个示），可以用一个0-1000-100的自然数来表示，数越大表示越好心。的自然数来表示，数越大表示越好心。小渊和小轩希望尽可能找好心程度高的同学来帮忙传纸条，即找小渊和小轩希望尽可能找好心程度高的同学来帮忙传纸条，即找到来回两条传递路径，使得这两条路径上同学的好心程度之和最到来回两条传递路径，使得这两条路径上同学的好心程度之和最大。现在，请你帮助小渊和小轩找到这样的两条路径。大。现在，请你帮助小渊和小轩找到这样的两条路径。【输入输入】输入文件输入文件message.inmessage.in的第一行有的第一行有2 2个个用空格隔开的整数用空格隔开的整数m m和和n n，表示班里有，表示班里有m m行行n n列列（1 1m,n m,n 50 50）。接下来的）。接下来的m m行是一个行是一个m*nm*n的的矩阵，矩阵中第矩阵，矩阵中第i i行行j j列的整数表示坐在第列的整数表示坐在第i i行行j j列的学生的好心程度。每行的列的学生的好心程度。每行的n n个整数之间用个整数之间用空格隔开。空格隔开。【输出输出】输出文件输出文件message.outmessage.out共一行，包含共一行，包含一个整数，表示来回两条路上参与传递纸条的一个整数，表示来回两条路上参与传递纸条的学生的好心程度之和的最大值。学生的好心程度之和的最大值。由于计算的可逆性，因此设两人从左上角走至右下角。两人分别走m+n-2步才能到达目的地；阶段i：两条路径的长度（2im+n-2），满足有序性要求；状态j,k：目前两条路径的行位置。显然，两条路径的列位置为 y1=i-j+1;y2=i-k+1（y1，y21n）由于两条路径不能重合，因此jk。最后1步前，两条路径分别在m行和m-1行 决策：第i步两条路径分别选择哪个方向走为最佳设状态转移方程fi,j,k为两条路径的当前长度为i、最后走到的行位置分别为j和k时的最大数和。走第走第i i步时有四种方案步时有四种方案 情况情况1 1：两条路径向右走，即fi-1,j,k+aj,y1+ak,y2 情况情况2 2：第1条路径向下走，第2条路径向右走，即 fi-1,j-1,k+aj,y1+ak,y2（j-1k）情况情况3 3：第2条路径向下走，第1条路径向右走，即 fi-1,j,k-1+aj,y1+ak,y2（jk-1）情况情况4 4：两条路径向下走,即 fi-1,j-1,k-1+aj,y1+ak,y2 显然，状态转移方程为 fi,j,k=max fi-1,j,k,fi-1,j-1,kj-1k,fi-1,j,k-1 jk-1,fi-1,j-1,k-1+aj,y1+ak,y2 最后输出fm+n-2,m,m-1。read(m,n);/*输入行数和列数输入行数和列数*/for i1 to m do/*读数字矩阵读数字矩阵*/for j1 to n do read(ai,j);fillchar(f,sizeof(f),0);for i2 to m+n-2 do /*延伸两条路径的长度延伸两条路径的长度*/for j1 to m do /*枚举两条路径的当前行位置枚举两条路径的当前行位置*/for k1 to m do y1i-j+1;y2i-k+1;/*计算两条路径的计算两条路径的当前列位置当前列位置*/if(not(y10)and(y20)and(y1=n)and(y2=n)or(j=k)then continue;/*若两条路径的若两条路径的当前列位置越出界外或者同处当前列位置越出界外或者同处一行的话，则继续枚举一行的话，则继续枚举*/fi,j,kmax(fi,j,k,fi-1,j,k);/*情况情况1：两条路径向右走：两条路径向右走*/if j-1k then fi,j,kmax(fi,j,k,fi-1,j-1,k);/*情况情况2：第：第1条路径向下走，条路径向下走，第第2条路径向右走条路径向右走*/if jk-1 then fi,j,kmax(fi,j,k,fi-1,j,k-1);/*情况情况3：第：第2条路径向下走，条路径向下走，第第1条路径向右走条路径向右走*/fi,j,kmax(fi,j,k,fi-1,j-1,k-1);/*情况情况4：两条路径向下走：两条路径向下走*/fi,j,kfi,j,k+aj,y1+ak,y2;/*取走（取走（j,y1）和（和（k,y2）的数字）的数字*/;/*for*/writeln(fm+n-2,m,m-1);/*输出两条路径上的最大数和输出两条路径上的最大数和*/最佳旅行路线问题最佳旅行路线问题 你在加拿大航空公司组织的一次竞赛中获奖，奖品是一张免费机票，可在加拿大旅行，从最西的一个城市1出发，单方向从西向东经若干城市到达最东的城市n（必须到达最东的城市n）；然后再单方向从东向西飞回起点城市1（可途径若干城市）。除起点城市1外，任何城市只能访问次，起点城市1被访问次：出发一次；返回一次。除指定的航线外，不允许乘其他航线也不允许使用其他交通工具。求解的问题是：给定城市表列及两城市之间的直通航线表列，请找出一条旅行路线，在满足上述限制条件下，使访问的城市数尽可能多。旅行路线问题满足旅行路线问题满足“无后效性原则无后效性原则”将旅行路线拆分成两条由东到西的航线。设阶段为P1,P2，即第1条航线目前到达城市p1，第2条航线目前到达城市p2。假如阶段P1,P2可到达阶段Q1,Q2，则必须满足的条件就是:P1Q1或P2j或者i=j=n时,i的前驱城市k；ij，或i=j=n时，到达i的前趋顶点k与j的两条路线的所需乘航线之和也一定最大，否则与fi，j最大矛盾。若ij时，结论同理可得。由此得出如下状态转移方程：f i，i 无意义(1in）最多可能的访问城市数为fn，n-2（减去最东和最西的城市被重复访问的次数），时间复杂度降为O（n2）。状态转移方程状态转移方程初始化初始化const maxn=1001;/*顶点数的上限顶点数的上限*/var g:array1.maxn,1.maxnof integer;/*顶点顶点i的第的第k个儿子的序号为个儿子的序号为gi,k*/b:array1.maxn of integer;/*度数表，顶点度数表，顶点i的度为的度为di*/f:array0.maxn,0.maxn of integer;/*状态转移方程，其中状态转移方程，其中fi,j为从顶点为从顶点1出出发的两条不相交的路线分别到达顶点发的两条不相交的路线分别到达顶点i与顶点与顶点j时，两路线的所需乘航线之和的最时，两路线的所需乘航线之和的最大值大值*/n:integer;/*顶点数顶点数*/proc init;/*输入信息，构造邻接表输入信息，构造邻接表*/var i,j:integer;readln(n);/*读顶点数读顶点数*/fillchar(b,sizeof(b),0);fillchar(g,sizeof(g),0);/*度数表和邻接表初始化度数表和邻接表初始化*/for i1 to n do read(j);/*读顶点读顶点i的第的第1个儿子个儿子*/while j0 do inc(bi);gi,bij;read(j);/*通过循环将顶点通过循环将顶点i连出的所有连出的所有边存入邻接表边存入邻接表*/readln;/*for*/fillchar(f,sizeof(f),0);/*状态转移方程初始化状态转移方程初始化*/;/*init*/通过动态规划计算和输出最多可能访问的顶点数通过动态规划计算和输出最多可能访问的顶点数proc make;var i,j,k:integer;for i1 to n do /*枚举每一对顶点枚举每一对顶点*/for j1 to n do if(i=1)and(j=1)then continue;/*若若i和和j同为出发点，则枚举下一对顶点同为出发点，则枚举下一对顶点*/if(ij)or(i=n)and(j=n)/*计算第一种情况计算第一种情况*/then for k1 to bi do /*枚举枚举i的每个前驱顶点，计算经由前驱顶点到的每个前驱顶点，计算经由前驱顶点到达顶点达顶点i和到达顶点和到达顶点j的最佳方案的最佳方案*/if gi,ki then fi,jmax(fi,j,fgi,k,j+1);continue;/*继续枚举下一对顶点继续枚举下一对顶点*/if ij /*计算第二种情况：枚举计算第二种情况：枚举j的每个前驱顶点，计算到达顶点的每个前驱顶点，计算到达顶点i和经由和经由前驱顶点到达顶点前驱顶点到达顶点j的最佳方案，从中找出到达顶点的最佳方案，从中找出到达顶点i和到达顶点和到达顶点j的最佳方案的最佳方案*/then for k1 to bj do if gj,k0 mod 43 mod 40 mod 4 (3+2)mod 4(3+1)mod 4 (3+2)mod 4(3+1)mod 4。但是我们可以把它转换成判定性问题，用递推法但是我们可以把它转换成判定性问题，用递推法来解决。来解决。设设f fk k(s(sk k)从从第第1 1点点到到第第k k点点的的长长度度mod mod 4 4为为s sk k的的路路径是否存在的标志。显然径是否存在的标志。显然 （边界条件）（边界条件）（这里（这里lenlenk,ik,i表示从第表示从第k-