动态规划(动态程序设计)-王建德课件

动态规划上海市控江中学王建德动态规划上海市控江中学王建德1动态规划上海市控江中学王建德动态规划上海市控江中学王建德讨论的问题1、动态规划的基本概念2、动态规划的基础题型3、动态规划的综合题型

讨论的问题1、动态规划的基本概念2讨论的问题1、动态规划的基本概念讨论的问题1、动态规划的基本基本概念动态程序设计是解决多阶段决策最优化问题的一种思想方法。所谓“动态”，指的是在问题的多阶段决策中，按某一顺序，根据每一步所选决策的不同，将随即引起状态的转移，最终在变化的状态中产生一个决策序列。动态规划就是为了使产生的决策序列在符合某种条件下达到最优。基本概念动态程序设计是解决多阶段决策最优化问题的一种思想方法3基本概念动态程序设计是解决多阶段决策最优化问题的一种思想方法DAGCKBNPOMJFHELI312345214323142212223344阶段1阶段2阶段3阶段4阶段5问题的引出：P是出发点，从P到A，求最短路径DAGCKBNPOMJFHELI312345214323144DAGCKBNPOMJFHELI31234521432314思路令

从PA的最短路径为P(A)；P(A)=min{P(B)+2,P(C)+3}；从PB的最短路径为P(B)；P(B)=min{P(D)+1,P(E)+2}；从PC的最短路径为P(C);P(C)=min{P(E)+5,P(F)+4}；‥‥‥‥‥‥思路令从PB的最短路径为P(B)；P(B)=min5思路令从PB的最短路径为P(B)；P(B)=min上述递推公式告诉我们，要求P(A)需要先求出阶段5中的P(B)和P(C)；要求P(B)(或者P(C)），又要先求出阶段4中的P(D)和P(E)(或P(F)和P(E))……（倒推） 显然，要依照上述递推过程求解，需要倒过来，从P(P)出发，先求出第一阶段的P(O)和P(N)，再求第二阶段的P(K)，P(L)，P(M)；……，最后得到P(A)（顺推）。上述递推公式告诉我们，要求P(A)需要先求出阶段5中的6上述递推公式告诉我们，要求P(A)需要先求出阶段5中的h[3][0]h[3][1]h[3][2]h[2][0]h[2][1]h[2][2]h[1][0]h[1][1]h[1][2]h[0][0]h[0][1]h[0][2]v[2][0]v[2][1]v[2][2]v[2][3]v[1][0]v[1][1]v[1][2]v[1][3]v[0][0]v[0][1]v[0][2]v[0][3](3,3)0213213yxh[3][0]h[3][1]h[3][2]h[2][0]h[7h[3][0]h[3][1]h[3][2]h[2][0]h[数据结构将每条路经的长度存在数组中东西方向上的道路长度存在两维数组h[4][3]中,规定数组的第一维为行号，第二维为列号。h[4][3]={{3,2,3},{2,1,4},{3,4,5},{3,1,2}};数据结构h[4][3]={{3,2,3},{2,1,4}8数据结构h[4][3]={{3,2,3},{2,1,4}南北方向上道路长度存至数组v[3][4]中，也规定第一维为行号，第二维为列号。v[3][4]={{2,2,3,4},{4,1,2,4},{1,2,2,3}};南北方向上道路长度存至数组v[3][4]中，也规定第一维为行9南北方向上道路长度存至数组v[3][4]中，也规定第一维为行求解过程为从(0,0)到(3,3)求最短路径问题定义二维数组，P[4][4]={{0,0,0,0},{0,0,0,0},{0,0,0,0},{0,0,0,0}},第一维为行，第二维为列。这时P(O)为P[0][1]；P(N)为P[1][0]；…P(A)为P[3][3]，以下为分阶段递推求解过程。P[0][0]=0;求解过程为从(0,0)到(3,3)求最短路径问题定义二维10求解过程为从(0,0)到(3,3)求最短路径问题定义二维阶段1:P[0][1]=P[0][0]+h[0][0]=0+3=3;P[1][0]=P[0][0]+v[0][0]=0+2=3;

阶段2:P[1][1]=min{P[0][1]+v[0][1],P[1][0]+h[1][0]}=min{3+1,2+2}=4P[0][2]=P[0][1]+h[1][0]=3+2=5;P[2][0]=P[1][0]+v[1][0]=2+4=6阶段3:P[1][2]=min{P[0][2]+v[0][2],P[1][1]+h[1][1]}=min{5+3,4+1}=5P[0][3]=P[0][2]+h[0][2]=5+3=8;P[3][0]=P[2][0]+v[2][0]=6+1=7P[2][1]=min{P[1][1]+v[1][1],P[2][0]+h[2][0]}=min{4+1,6+1}=5阶段4:P[1][3]=min{P[0][3]+v[0][3],P[1][2]+h[1][2]}=min{8+4,5+4}=9P[2][2]=min{P[1][2]+v[1][2],P[2][1]+h[2][1]}=min{5+2,5+4}=7P[3][1]=min{P[2][1]+v[2][1],P[3][0]+h[3][0]}=min{5+2,7+3}=7阶段5:P[2][3]=min{P[1][3]+v[1][3],P[2][2]+h[2][2]}=min{9+4,7+5}=12P[3][2]=min{P[2][2]+v[2][2],P[3][1]+h[3][1]}=min{7+2,7+1}=8最后:P[3][3]=min{P[2][3]+v[2][3],P[3][2]+h[3][2]}=min/*12+3,8+2}=10阶段1:P[0][1]=P[0][0]+h[0]11阶段1:P[0][1]=P[0][0]+h[0]综上，数组P的通项表示为P[i][j]=min((p[i-1][j]+v[i-1][j]),(p[i][j-1]+h[i][j-1]))(i,j>0)P[0][j]=P[0][j-1]+h[0][j-1] (i=0,j>0)P[i][0]=P[i-1][0]+v[i-1][0] (i>0,j=0)P数组数据圆圈内为路口对P点的最小距离,箭头为最佳行走路径。综上，数组P的通项表示为P数组数据圆圈内为路口对P点的最小距12综上，数组P的通项表示为P数组数据圆圈内为路口对P点的最小距forj←

1to4do/*计算0行上的每点的距离*/p[0][j]←

p[0][j-1]+h[0][j-1];Fori←

1to4do/*计算0列上的每点的距离*/p[i][0]←

p[i-1][0]+v[i-1][0];fori←

1to4do forj←

1to4dop[i][j]←min((p[i-1][j]+v[i-1][j]),(p[i][j-1]+h[i][j-1]));Fori←3downto0do/*输出每个路口对P点的最小距离*/{forj←

0to3dowrite(p[i][j]:4)writeln;};/*for*/

程序forj←1to4do13forj←1to4do阶段：据空间顺序或时间顺序对问题的求解划分阶段。状态：描述事物的性质，不同事物有不同的性质，因而用不同的状态来刻画。对问题的求解状态的描述是分阶段的。决策：根据题意要求，对每个阶段所做出的某种选择性操作。状态转移方程：用数学公式描述与阶段相关的状态间的演变规律。多阶段决策过程：将所研究的过程划分为若干个相互联系的阶段，在求解时，对每一个阶段都要做出决策，前一个决策确定以后，常常会影响下一个阶段的决策。动态规划的几个要素阶段：据空间顺序或时间顺序对问题的求解划分阶段。动态规14阶段：据空间顺序或时间顺序对问题的求解划分阶段。动态规“最优性原理”：不论初始状态和第一步决策是什么，余下的决策相对于前一次决策所产生的新状态，构成一个最优决策序列。最优决策序列的子序列，一定是局部最优决策子序列。注意包含有非局部最优的决策子序列，一定不是最优决策序列,例如贪心法。动态规划的依据——“最优性原理”“最优性原理”：不论初始状态和第一步决策是什么15“最优性原理”：不论初始状态和第一步决策是什么动态规划的指导思想在做每一步决策时，列出各种可能的局部解，之后依据某种判定条件，舍弃那些肯定不能得到最优解的局部解。这样，在每一步都经过筛选，以每一步都是最优的来保证全局是最优的。筛选相当于最大限度地有效剪枝（从搜索角度看），效率会十分高。但它又不同于贪心法。贪心法:产生一个按贪心策略形成的判定序列，该序列不保证解是全局最优的，因为有些问题不符合最优性原理。动态规划:产生许多判定序列，再按最优性原理对这些序列加以筛选，去除那些非局部最优的子序列。动态规划的指导思想在做每一步决策时，列出各种可能的局部解，之16动态规划的指导思想在做每一步决策时，列出各种可能的局部解，之2、动态规划的基础题型1、路径问题2、01背包问题3、求最佳子序列问题4、双重动态规划2、动态规划的基础题型1、路径问题172、动态规划的基础题型1、路径问题2、动态规划的基础题型1、路径问题的讨论问题的一般形式：1、计算所有路径方案2、计算一条最佳路径

3、计算两条最佳路径（多进程的最优化决策）一般方法：按照出发点走出的步数划分阶段，将当前步可达的顶点集定义为状态，当前步如何走定义为决策。注意：1、可能需要将原题转化为路径问题2、如果最佳路径问题不满足最优子结构特征特征的话，可以转化为判定性问题求解。路径问题的讨论问题的一般形式：18路径问题的讨论问题的一般形式：路径问题的讨论问题的一般形式：一、计算所有方案对于一些阶段性强、但不属于最优化的问题，是否也可以借助动态规划方法呢？如果我们可以找出状态转移的关系，并在状态转移方程

中去掉最佳性要求opt（min或max），将扩展子状态的所有行动作为决策，则可以例举出由初始状态至目标状态的所有方案。显然，在计数类问题中使用这种方法要比回溯法等搜索算法简捷许多。一、计算所有方案对于一些阶段性强、但不属于最优化的问19一、计算所有方案对于一些阶段性强、但不属于最优化的问例题过河卒如图，A点有一个过河卒，需要走到目标B点。卒行走的规则：可以向下、或者向右。

例题过河卒如图，A点有一个过河卒，需要走到目标B点20例题过河卒如图，A点有一个过河卒，需要走到目标B点同时在棋盘上的任一点有一个对方的马（如上图的C点）,该马所在的点和所有跳跃一步可达的点称为对方马的控制点。例如上图C点上的马可以控制8个点（图中的P1，P2….P8）。卒不能通过对方马的控制点。棋盘用坐标表示，A点（0，0）、B点（n，m）(n,m为不超过20的整数,并由键盘输入)，同样马的位置坐标是需要给出的（约定：C≠A，同时C≠B）。现在要求你计算出卒从A点能够到达B点的路径的条数。输入：键盘输入B点的坐标(n,m)以及对方马的坐标（X，Y）输出：屏幕输出一个整数（路径的条数）。同时在棋盘上的任一点有一个对方的马（如上图的C点）,21同时在棋盘上的任一点有一个对方的马（如上图的C点）,按照题意，对方的马所在的点和所有跳跃一步可达的点称为对方马的控制点，卒不能通过对方马的控制点。在卒出发之前，必须计算对方马的所有控制点。显然，若（0，0）或（n,m）为控制点，则输出路径数为0。设constmove:array[1..8,1..2]ofinteger/*move[k，1..2]为马沿k方向跳跃一步的水平增量和垂直增量*/=((1,-2),(1,2),(2,1),(2,-1),(-1,2),(-1,-2),(-2,1),(-2,-1))；varlist:array[-1..20,-1..20]ofcomp；/*list[i,j]为卒从(0,0)到(i,j)的路径数*/can:array[0..20,0..20]ofboolean；/*can[i,j]为允许卒通行(i,j)的标志*/1、计算对方马的控制点

按照题意，对方的马所在的点和所有跳跃一步可达的点称为对方马的22按照题意，对方的马所在的点和所有跳跃一步可达的点称为对方马的设马的初始位置为（x,y）。按照下述方式计算can序列can[x,y]←false；/*对方马所在的点为控制点*/fori←1to8do/*从（x，y）出发，沿8个方向计算控制点*/{j←x+move[i,1]；/*计算i方向的跳马位置(j，k)*/k←y+move[i,2]；if(j>=0)and(k>=0)and(j<=n)and(k<=m)/*若（j,k）在界内，则为控制点*/thencan[j,k]←false；}；/*for*/if(notcan[0,0])or(notcan[n,m])/*若卒的起点和终点为控制点，则输出路径数0*/thenwriteln(0)else{计算和输出卒从（0，0）走到（n,m）点的路径数list[n,m]}；/*else*/设马的初始位置为（x,y）。按照下述方式计算can序列can23设马的初始位置为（x,y）。按照下述方式计算can序列can我们按照由上而下、由左而右的顺序，将卒可能到达的每一个位置（i,j）(0≤i≤n，0≤j≤m)设为阶段和状态。首先，将卒的出发点（0，0）的路径数设为1，该位置设为控制点（list[0,0]←1;can[0,0]←fals）。然后从（0，0）出发，按照由上而下、由左而右的顺序计算卒经过每一个可行点的路径数:若（i，j）为可行点，则走前位置（i-1,j）和（i,j-1）的路径数加起来，即为从（0，0）走到（i，j）的路径数，即list[i,j]=list[i-1,j]+list[i,j-1]∣（i，j）非控制点依次类推，最后得出的list[n,m]即为问题的解。由此得出算法：fillchar(list,sizeof(list),0)；/*路径数序列初始化*/list[0,0]←1；can[0,0]←false；/*卒从（0，0）出发的路径数为1，该位置不再允许卒通行*/fori←0tondo/*按照由上而下、由左而右计算从(0,0)到每个可行点的路径数*/forj←0tomdoifcan[i,j]thenlist[i,j]←list[i-1,j]+list[i,j-1]；输出卒从（0，0）走到（n,m）点的路径条数list[n,m]；2、计算和输出卒从（0，0）走到（n,m）点的路径条数我们按照由上而下、由左而右的顺序，将卒可能到达的每一24我们按照由上而下、由左而右的顺序，将卒可能到达的每一计算一条最佳路径以路径长度划分阶段，从出发点走i步可达的顶点集合为状态。设f[i,j]为到达阶段i的顶点j的最优解。枚举第i-1阶段中与状态j相连的状态k,其子问题的最优解f[i-1,k]+状态k至状态j的决策代价wk,j即为阶段i的状态j的一种方案。枚举了所有可能方案后即可得出f[i,j]。f[i-1,k1]Wk1,jf[i-1,k2]Wk2,jf[i-1,kp]Wkp,j计算一条最佳路径以路径长度划分阶段，从出发点走i步可达的顶点25计算一条最佳路径以路径长度划分阶段，从出发点走i步可达的顶点寻宝游戏

寻宝游戏26寻宝游戏寻宝游戏26分析在“藏宝图”中寻求一条含len个顶点的路径，使得∑(1≤k≤len)((xk,yk)-ak)2最小。分析在“藏宝图”中寻求一条含len个顶点的路径，使得∑(1≤27分析在“藏宝图”中寻求一条含len个顶点的路径，使得∑(1≤数据结构

constex:array[1..4]ofshortint=(0,0,1,-1);ey:array[1..4]ofshortint=(1,-1,0,0);varn,m,len,i,j,k,l,i0,j0:integer;/*n,m为“藏宝图”的规模*/mp:array[1..50,1..50]ofinteger;/*“藏宝图”*/c0,c1:array[1..50,1..50]oflongint;/*c0〔I,j〕为c[k-1,I,j];c1〔I,j〕为c[k,I,j]*/a:array[1..150]ofinteger;/*数列*/ans:longint;/*数列与表格的接近程度*/数据结构

const28数据结构

const数据结构

const28输入信息，计算c0的初始值readln(f,n,m);/*输入“藏宝图”的规模*/fori←1tondo/*输入“藏宝图”*/forj←1tomdoread(f,mp[i,j]);readln(f,len);/*输入数列的项数len*/fori←1tolendoread(f,a[i]);/*输入数列*/fori←1tondo/*计算初始解*/forj←1tomdoc0[i,j]←sqr(a[1]-mp[i,j]);输入信息，计算c0的初始值readln(f,n,m);29输入信息，计算c0的初始值readln(f,n,m);fork←2tolendo/*阶段:路径长度*/{fori←1tondo/*状态:当前位置*/forj←1tomdo{c1[i,j]←maxint;forl←1to4do/*决策:选择最佳移前位置*/{i0←i+ex[l];j0←j+ey[l];if(i0in[1..n])and(j0in[1..m])and(c0[i0,j0]<c1[i,j])thenc1[i,j]←c0[i0,j0]};/*for*/c1[i,j]←c1[i,j]+sqr(mp[i,j]-a[k])};/*for*/c0←c1};/*for*/ans←maxint;/*计算ans＝min｛c1[I,j]｝*/fori←1tondoforj←1tomdoifc1[i,j]<ansthenans←c1[i,j];writeln(,ans)/*输出数列与表格的接近程度*/fork←2tolendo30fork←2tolendoHanoi双塔问题

【问题描述】给定A,B,C三根足够长的细柱，在A柱上放有2n个中间有空的圆盘，共有n个不同的尺寸，每个尺寸都有两个相同的圆盘，注意这两个圆盘是不加区分的(下图为n=3的情形）。现要将这些国盘移到C柱上，在移动过程中可放在B柱上暂存。要求:

(1)每次只能移动一个圆盘；

(2)A、B、C三根细柱上的圆盘都要保持上小下大的顺序；

任务:设An为2n个圆盘完成上述任务所需的最少移动次数，对于输入的n，输出An。

【输入】输入文件hanoi.in为一个正整数n，表示在A柱上放有2n个圆盘。

【输出】输出文件hanoi.out仅一行，包含一个正整数，为完成上述任务所需的最少移动次数An。

Hanoi双塔问题

【问题描述】给定A,B,C三根足够长31Hanoi双塔问题

【问题描述】给定A,B,C三根足够长转化为一条路径问题若将盘子作为顶点，且按照移动规则，将前i个尺寸的盘子移动到目标柱的最少步数作为最短路径长度，则可以将双塔问题转化为最佳路径问题。注意：由于移动规律唯一，因此决策和状态转移也是唯一的，动态规划变成递推题。转化为一条路径问题若将盘子作为顶点，且按照移动规则，将前i个32转化为一条路径问题若将盘子作为顶点，且按照移动规则，将前i个状态转移方程按照移动规则的有序性，前i个尺寸的盘子作为阶段（2≤i≤n），第i个尺寸的盘子作为状态。设f[i]代表i个尺寸的盘子移动到目标柱的最少步数。决策为三个移动步骤：1、把前i-1尺寸的个盘子由起始柱移动到中间柱，移动步数为f[i-1]；2、把第i个尺寸的盘子由起始柱移动到目标柱，移动步数为2；3、把前i-1个尺寸的盘子由中间柱移动到目标柱，移动步数为f[i-1]。状态转移方程：边界：f[1]=2由于n的上限为200，因此需要采用高精度加法和高精度乘法运算。为了确保不超时，建议按照104进制存储。状态转移方程按照移动规则的有序性，前i个尺寸的盘子作为阶段（33状态转移方程按照移动规则的有序性，前i个尺寸的盘子作为阶段（采药

【问题描述】辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”如果你是辰辰，你能完成这个任务吗？【输入文件】输入文件medic.in的第一行有两个整数T（1≤T≤1000）和M（1≤M≤100），用一个空格隔开，T代表总共能够用来采药的时间，M代表山洞里的草药的数目。接下来的M行每行包括两个在1到100之间（包括1和100）的整数，分别表示采摘某株草药的时间和这株草药的价值。【输出文件】输出文件medic.out包括一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。采药

【问题描述】辰辰是个天资聪颖的孩子，他的梦想是成为世界34采药

【问题描述】辰辰是个天资聪颖的孩子，他的梦想是成为世界转化为一条路径问题将时间作为顶点，该段时间内采到的最大草药总价值作为路径长度的最佳值，因此可以将采药问题转化为最佳路径问题。注意：1、每株草药可采可不采，且采摘时间任意2、最后一株草药采摘的结束时间未定，因此最后需要枚举[0，t]中每段时间内采到的最大草药总价值，从中找到解转化为一条路径问题将时间作为顶点，该段时间内采到的最大草药总35转化为一条路径问题将时间作为顶点，该段时间内采到的最大草药总采用动态规划方法解题阶段i:依次考虑前i株草药(1≤i≤m);状态j:采摘第i株草药的结束时间(x≤j≤t);决策k:什么时候采摘第i株草药可使得k+x时刻内可采到的草药总价值最大。由于草药的采摘时间任意，因此0≤k≤t-x;设a[j]为j时间内可采到的草药的最大总价值，第i株草药的采摘时间为x、价值为y。开始采摘第i株草药的时刻j的可能范围为[0，t-x]，采完第i株草药的时刻为j+x。在该时间内内可采到的草药的最大总价值a[j+x]=显然，在t时间内可以采到的草药的最大总价值ans=采用动态规划方法解题阶段i:依次考虑前i株草药(1≤i≤m)36采用动态规划方法解题阶段i:依次考虑前i株草药(1≤i≤m)vara:array[0..1000]oflongint;/*a[j]为j时间内可采到的草药的最大总价值a[j+x]=*/t,m,i,j,x,y,ans:longint;{readln(t,m);/*输入采药时间和草药数*/fori←1totdoa[i]←

-1;a[0]←

0;fori←1tomdo/*逐株采摘草药*/{readln(x,y);/*输入采摘第i株草药的时间和价值*/forj←

t-xdownto0do/*枚举开始采摘第i株草药的时刻*/if(a[j]>=0)and(a[j+x]<a[j]+y)thena[j+x]←a[j]+y};/*for*/ans←

-1;/*在t时间内采到草药的最大总价值ans=*/fori←

0totdoifans<a[i]thenans←

a[i];writeln(ans);/*输出t时间内可采到的草药的最大总价值*/}.var37varvar37Chain

拜特兰并不总是一个非常民主的国家，也有一些阴暗的历史。一个美好的日子，拜特将军－该国的统帅作了一个用以结束长期内战的决定，释放被关押的反对派。然而，他并未让反对派的领袖拜特萨直接自由，而是用一根“拜特链”将拜特萨锁在墙边.该链子由很多环和固定在墙上栅栏组成。尽管环并未和栅栏融合在一起，但想除去它们却非常困难。“将军，你为什么要用链子将我锁在墙边而不让我自由！”拜特萨大叫道。“拜特萨，你并未完全被链子锁住，我可以坦率的告诉你，你完全可以从栅栏上解下环。”拜特将军不忠地回答，同时他补充说，“但是，你必须在夜里工作，一个小时之内完成，不能弄出任何声音，否则，我将按有关法律制罪。”。为了帮助拜特萨！链子上的环按整数1,2,…,n进行了编号。我们可以按照以下规则解开环：只有一个环时可以被连接到栅栏或从栅栏上拆开。第1号环总能进行连接或拆开如果1,...,k-1(1<=k<n)环都被拆开，第k个环被连接时,此时我们能连接或拆开第k+1个环.

Chain拜特兰并不总是一个非常民主的国家，也有一些阴暗的38Chain拜特兰并不总是一个非常民主的国家，也有一些阴暗的写一个程序：文本文件LAN.IN描述了拜特链的构成,计算拆除拜特链上全部环的最少操作次数,将结果写入文本文件LAN.OUT.

输入：在文本文件LAN.IN中的第1行有一个整数n,1<=n<=1

000.在第2行有n个用一个空格分隔的整数o1,o2,...,on(每个都是0或1)，如果oi=1,那么第I个环和栅栏相连，如果oi=0,那么第I环没有和栅栏相连。输出：文本文件LAN.OUT中只包含一个整数，为解开拜特链的全部环的最少操作次数。写一个程序：文本文件LAN.IN描述了拜特链的构成,计算拆除39写一个程序：文本文件LAN.IN描述了拜特链的构成,计算拆除转化为一条路径问题拜特链为一条长度为n的01串s。如果将s中长度为i的后缀（或前缀）看作是顶点i，将该子串全部变换到0所需的操作次数看作是初始串至顶点i的路径长度，则可以将Chain问题转化为初始串至顶点n的最短路问题。注意:通过分析解环的规律优化算法转化为一条路径问题拜特链为一条长度为n的01串s。如果将s中40转化为一条路径问题拜特链为一条长度为n的01串s。如果将s中重述题目任意给定一个01串S，以及下面两种操作：操作a：将S的第一个字符取反。操作b：若S[1..i–1]=‘000…00’，S[i]=‘1’，那么将S[i+1]取反（1≤i≤n–1）同时给出一个固定的目标串T=‘0000…00’。现在需要将初始串S反复执行上述两种操作，变换到目标串T。问：至少需要执行多少次操作？重述题目任意给定一个01串S，以及下面两种操作：41重述题目任意给定一个01串S，以及下面两种操作：重述题目任意譬如S=‘1010’执行操作b：1110执行操作a：0110执行操作b：0100执行操作a：1100执行操作b：1000执行操作a：0000共进行了6次操作。譬如S=‘1010’执行操作b：111042譬如S=‘1010’执行操作b：1110譬如S=‘1由规律引出最简单的算法性质1同一种操作不能连续两次执行。证明：若连续执行同一操作两次，相当于没执行任何操作。所以不能将同一种操作连续两次执行。根据性质1，我们容易得到：性质2将S变换到T的操作序列必然是：操作序列1：abab……ba或者操作序列2：baba……ba（最后执行的操作必然是a）引出最简单的算法：分别按照上述两种方法对S进行操作，得出所需得操作次数；取较小值作为答案。这种算法的效率十分低下。如果最后的结果是s，那么它的时间复杂度就是O(s)——s最大可以达到2n！

由规律引出最简单的算法性质1同一种操作不能连续两次执行。43由规律引出最简单的算法性质1同一种操作不能连续两次执行。由要将S的每一位都变成0，显然最后一次执行的必须是操作a。故而我们可以将整个变换过程分解成：S1000…00000…00,即将S的后n-1位全变为0。将S的第1位变为0。要将S的每一位都变成0，显然最后一次执行的必须是操作a。故而44要将S的每一位都变成0，显然最后一次执行的必须是操作a。故而图中左列是S=’1010’变到T=’0000’的过程。我们如果只关心它的后n-1位，实际上是把S的后3位变换到“全零”的过程。1、后面n-1位的变换又直接受到第一位取值的影响：当第一位为0时，后n-1位才能进行操作序列2（ba‥‥）；当第一位为1时，后n-1位才能进行操作序列1（ab‥‥）。2、对后n-1位进行变换同样要遵行性质2（ab交替出现）。所以对后n-1位执行完一次操作a，就必须进行一次额外的操作，将原串的第一位取反；类似的，对后n-1位执行完一次操作b，也必须进行一次额外的操作，将原串中的第一位取反（即后n-1位的一次操作对应操作ba,使得后n-1位的每个状态都重复出现了两次）。图中左列是S=’1010’变到T=’0000’的过程45图中左列是S=’1010’变到T=’0000’的过程状态转移方程S的后缀长度i(1≤i≤n)为阶段，操作k为状态(k=1,2)。由于解环规律是唯一的，因此决策也是唯一的。设f[i,1]——通过“操作序列1”将S的后i位全部变换到0所需的最少操作次数；f[i,2]——通过“操作序列2”将S的后i位全部变换到0所需的最少操作次数。状态转移方程：当第n-i+1位是1时，有两种情况：①通过a将第n-i+1位变0，然后对后i-1位进行操作2，即f[i,1]=f[i-1,2]*2+1；②直接对f后i-1位进行操作1，即[i,2]=f[i-1,1]*2当第n-i+1位是0时，有两种情况：①通过a将第n-i+1位变1，然后对后i-1位进行操作1，即f[i,1]=f[i-1,1]*2+1；②直接对后i-1位进行操作2，即[f[i,2]=f[i-1,2]*2边界条件：f[0,1]=+∞，f[0,2]=0解：min{f[n,2],f[n,1]}。由于结果可能很大，所以要使用高精度运算。算法时间复杂度是O(n)。（不包括高精度运算）状态转移方程S的后缀长度i(1≤i≤n)为阶段，操作k为状态46状态转移方程S的后缀长度i(1≤i≤n)为阶段，操作k为状态漂亮打印

漂亮打印

47漂亮打印

漂亮打印

47将当前行k的尾单词序号i作为顶点,这种情况下第1行至第k行的“漂亮”标准作为路长。设

c[k,i]为前k行、尾单词为i时的“漂亮”标准。若第k-1行的尾单词序号为j,则第k行的单词序号为区间[j+1..i]，“漂亮”标准为（m-j+i-(∑(i≤k≤j)lk）)3。由此得出c[k,i]=c[k-1,j]+（m-j+i-(∑(i≤k≤j)lk）)3显然，必须预先计算出单词i..单词j的长度（期间含j-i个空格）lg[i,j]和最后一行的起始单词序号cn将当前行k的尾单词序号i作为顶点,这种情况下第1行至第k行的48将当前行k的尾单词序号i作为顶点,这种情况下第1行至第k行的数据结构varn,m,i,j,k,cn,ak,ai:integer;/*单词数为n,行宽为m，最后一行的起始单词序号为cn；倒数第2行的行序号为ak，该行的最后一个单词为ai*/ans:longint;/*目前为止的“漂亮”值*/l:array[0..max]ofinteger;/*单词的长度序列*/c:array[0..max,0..max]oflongint;/*c[k,i]为前k行、尾单词为i时的“漂亮”标准*/lg:array[0..max,0..max]ofinteger;/*lg[i，j]为单词i..单词j的长度,含空格*/数据结构var49数据结构var数据结构var49计算lg和最后一行的起始单词序号cn

readln(f,n,m);/*读单词树n和行宽*/fori←1tondoread(f,l[i]);/*读每个单词的长度*/l[0]←m;/*计算lg*/fori←0tondo{k←l[i];lg[i,i]←k;forj←i+1tondo{k←k+l[j]+1;lg[i,j]←k}/*for*/};/*for*/fori←ndownto0doiflg[i,n]>mthenbreak;/*计算最后一行的起始单词序号cn*/cn←i;inc(cn);ifcn>n/*若单词n的长度超过m，失败退出*/then{writeln(f0,'Printisimpossible.');continue};ifcn=1/*若n个单词的长度不足一行，则输出结果*/then{writeln(f0,0);writeln(f0,'Line1:',n);continue};/*then*/计算lg和最后一行的起始单词序号cn

readln(f,n,50计算lg和最后一行的起始单词序号cn

readln(f,n,动态程序设计动态程序设计51动态程序设计动态程序设计51ans←maxint;fori←1tondoc[0,i]←maxint;c[0,0]←0;fork←1ton-1do/*递推每一行*/{fori←0tok-1doc[k,i]←maxint;/*前k行的状态转移方程初始化*/fori←kton-1do/*枚举第k行的尾单词*/{c[k,i]←maxint;forj←i-1downtok-1do/*枚举第k-1行的尾单词*/if(lg[j+1,i]<=m)and(c[k-1,j]+(m-lg[j+1,i])3<c[k,i])thenc[k,i]←c[k-1,j]+(m-lg[j+1,i])3};/*for*/fori←cn-1ton-1do/*记录目前最“漂亮值”和方案*/ifc[k,i]<ansthen{ans←c[k,i];ak←k;ai←i}/*then*/};/*for*/ans←maxint;52ans←maxint;ans←maxint;52输出方案procedureputout(k,i:integer);/*前k行为前i个单词。输出该方案*/varj:integer;{ifk=0thenexit;/*递归边界*/forj←i-1downtok-1do/*计算第k-1行的尾单词j*/if(lg[j+1,i]<=m)and(c[k-1,j]+(m-lg[j+1,i])3=c[k,i])thenbreak;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)/*输出最后一行的单词数*/输出方案procedureputout(k,i:integ53输出方案procedureputout(k,i:integ一般有两种题型：1、2条最佳路径经过顶点的权和最大。需要优化状态的存储方式2、2条最佳路径经过的顶点数最多。计算2条最佳路径一般有两种题型：计算2条最佳路径54一般有两种题型：计算2条最佳路径一般有两种题型：计算2条最佳传纸条

【问题描述】小渊和小轩是好朋友也是同班同学，他们在一起总有谈不完的话题。一次素质拓展活动中，班上同学安排做成一个m行n列的矩阵，而小渊和小轩被安排在矩阵对角线的两端，因此，他们就无法直接交谈了。幸运的是，他们可以通过传纸条来进行交流。纸条要经由许多同学传到对方手里，小渊坐在矩阵的左上角，坐标(1,1)，小轩坐在矩阵的右下角，坐标(m,n)。从小渊传到小轩的纸条只可以向下或者向右传递，从小轩传给小渊的纸条只可以向上或者向左传递。在活动进行中，小渊希望给小轩传递一张纸条，同时希望小轩给他回复。班里每个同学都可以帮他们传递，但只会帮他们一次，也就是说如果此人在小渊递给小轩纸条的时候帮忙，那么在小轩递给小渊的时候就不会再帮忙。反之亦然。还有一件事情需要注意，全班每个同学愿意帮忙的好感度有高有低（注意：小渊和小轩的好心程度没有定义，输入时用0表示），可以用一个0-100的自然数来表示，数越大表示越好心。小渊和小轩希望尽可能找好心程度高的同学来帮忙传纸条，即找到来回两条传递路径，使得这两条路径上同学的好心程度之和最大。现在，请你帮助小渊和小轩找到这样的两条路径。传纸条

【问题描述】小渊和小轩是好朋友也是同班同学，他们在一55传纸条

【问题描述】小渊和小轩是好朋友也是同班同学，他们在一【输入】输入文件message.in的第一行有2个用空格隔开的整数m和n，表示班里有m行n列（1≤m,n≤50）。接下来的m行是一个m*n的矩阵，矩阵中第i行j列的整数表示坐在第i行j列的学生的好心程度。每行的n个整数之间用空格隔开。【输出】输出文件message.out共一行，包含一个整数，表示来回两条路上参与传递纸条的学生的好心程度之和的最大值。【输入】输入文件message.in的第一行有2个用空格隔开56【输入】输入文件message.in的第一行有2个用空格隔开由于计算的可逆性，因此设两人从左上角走至右下角。两人分别走m+n-2步才能到达目的地；阶段i：两条路径的长度（2≤i≤m+n-2），满足有序性要求；状态j,k：目前两条路径的行位置。显然，两条路径的列位置为

y1=i-j+1;y2=i-k+1（y1，y2∈[1‥n]）由于两条路径不能重合，因此j≠k。最后1步前，两条路径分别在m行和m-1行决策：第i步两条路径分别选择哪个方向走为最佳设状态转移方程f[i,j,k]为两条路径的当前长度为i、最后走到的行位置分别为j和k时的最大数和。由于计算的可逆性，因此设两人从左上角走至右下角。两人分别走m57由于计算的可逆性，因此设两人从左上角走至右下角。两人分别走m走第i步时有四种方案

情况1：两条路径向右走，即f[i-1,j,k]+a[j,y1]+a[k,y2]情况2：第1条路径向下走，第2条路径向右走，即

f[i-1,j-1,k]+a[j,y1]+a[k,y2]（j-1<>k）

情况3：第2条路径向下走，第1条路径向右走，即

f[i-1,j,k-1]+a[j,y1]+a[k,y2]（j<>k-1）

情况4：两条路径向下走,即

f[i-1,j-1,k-1]+a[j,y1]+a[k,y2]显然，状态转移方程为

f[i,j,k]=max{f[i-1,j,k],f[i-1,j-1,k]∣j-1<>k,f[i-1,j,k-1]∣j<>k-1,f[i-1,j-1,k-1]}+a[j,y1]+a[k,y2]最后输出f[m+n-2,m,m-1]。走第i步时有四种方案情况1：两条路径向右走，即f[i-158走第i步时有四种方案情况1：两条路径向右走，即f[i-1read(m,n);/*输入行数和列数*/fori←1tomdo/*读数字矩阵*/forj←1tondoread(a[i,j]);fillchar(f,sizeof(f),0);fori←2tom+n-2do/*延伸两条路径的长度*/forj←1tomdo/*枚举两条路径的当前行位置*/fork←1tomdo{y1←i-j+1;y2←i-k+1;/*计算两条路径的当前列位置*/if(not((y1>0)and(y2>0)and(y1<=n)and(y2<=n)))or(j=k)thencontinue;/*若两条路径的当前列位置越出界外或者同处一行的话，则继续枚举*/f[i,j,k]←max(f[i,j,k],f[i-1,j,k]);/*情况1：两条路径向右走*/ifj-1<>kthenf[i,j,k]←max(f[i,j,k],f[i-1,j-1,k]);/*情况2：第1条路径向下走，第2条路径向右走*/ifj<>k-1thenf[i,j,k]←max(f[i,j,k],f[i-1,j,k-1]);/*情况3：第2条路径向下走，第1条路径向右走*/f[i,j,k]←max(f[i,j,k],f[i-1,j-1,k-1]);/*情况4：两条路径向下走*/f[i,j,k]←f[i,j,k]+a[j,y1]+a[k,y2];/*取走（j,y1）和（k,y2）的数字*/};/*for*/writeln(f[m+n-2,m,m-1]);/*输出两条路径上的最大数和*/

read(m,n);/*输入行数和列数*/59read(m,n);/*输入行数和列数*/read(m,n)最佳旅行路线问题

你在加拿大航空公司组织的一次竞赛中获奖，奖品是一张免费机票，可在加拿大旅行，从最西的一个城市1出发，单方向从西向东经若干城市到达最东的城市n（必须到达最东的城市n）；然后再单方向从东向西飞回起点城市1（可途径若干城市）。除起点城市1外，任何城市只能访问１次，起点城市1被访问２次：出发一次；返回一次。除指定的航线外，不允许乘其他航线也不允许使用其他交通工具。求解的问题是：给定城市表列及两城市之间的直通航线表列，请找出一条旅行路线，在满足上述限制条件下，使访问的城市数尽可能多。最佳旅行路线问题

你在加拿大航空公司组织的一次竞赛中获奖，60最佳旅行路线问题

你在加拿大航空公司组织的一次竞赛中获奖，旅行路线问题满足“无后效性原则”将旅行路线拆分成两条由东到西的航线。设阶段为[P1,P2]，即第1条航线目前到达城市p1，第2条航线目前到达城市p2。假如阶段[P1,P2]可到达阶段[Q1,Q2]，则必须满足的条件就是:P1<Q1或P2<Q2。例如，阶段[3,4]中的道路可以加边(4,5)得出阶段[3,5]，而阶段[3,5]不可达阶段[3,4]，因为旅行路线要求必须严格地由左到右来旅行。若要计算阶段[i,j]经过的城市数，则阶段[i,k](或[k,j]经过的城市数已知。旅行路线问题满足“无后效性原则”将旅行路线拆分成两条61旅行路线问题满足“无后效性原则”将旅行路线拆分成两条因此旅行路线问题满足“无后效性原则”，可以用“动态规划”算法来解决。阶段i和j：第1条航线以城市i为尾、第2条航线以城市j为尾(1≤i,j≤n)状态i和j：当前两条航线的最后城市i和j决策k：i>j或者i=j=n时,i的前驱城市k；i<j时j的前驱城市k。究竟应选择哪个前驱城市k才可使得两条航线经过的城市数最多。因此旅行路线问题满足“无后效性原则”，可以用“动态规划”算法62因此旅行路线问题满足“无后效性原则”，可以用“动态规划”算法设f[i，j]为从顶点1出发的两条不相交的路线分别到达顶点i与顶点j时，两路线的所需乘航线之和的最大值。有两种情况，若i>j，或i=j=n时，到达i的前趋顶点k与j的两条路线的所需乘航线之和也一定最大，否则与f[i，j]最大矛盾。若i<j时，结论同理可得。由此得出如下状态转移方程：f[i，i]无意义(1<i<n）最多可能的访问城市数为f[n，n]-2（减去最东和最西的城市被重复访问的次数），时间复杂度降为O（n2）。

状态转移方程设f[i，j]为从顶点1出发的两条不相交的路线分别到达顶63设f[i，j]为从顶点1出发的两条不相交的路线分别到达顶初始化constmaxn=1001;/*顶点数的上限*/varg:array[1..maxn,1..maxn]ofinteger;/*顶点i的第k个儿子的序号为g[i,k]*/b:array[1..maxn]ofinteger;/*度数表，顶点i的度为d[i]*/f:array[0..maxn,0..maxn]ofinteger;/*状态转移方程，其中f[i,j]为从顶点1出发的两条不相交的路线分别到达顶点i与顶点j时，两路线的所需乘航线之和的最大值*/n:integer;/*顶点数*/procinit;/*输入信息，构造邻接表*/vari,j:integer;{readln(n);/*读顶点数*/fillchar(b,sizeof(b),0);fillchar(g,sizeof(g),0);/*度数表和邻接表初始化*/fori←1tondo{read(j);/*读顶点i的第1个儿子*/whilej<>0do{inc(b[i]);g[i,b[i]]←j;read(j)};/*通过循环将顶点i连出的所有边存入邻接表*/readln};/*for*/fillchar(f,sizeof(f),0);/*状态转移方程初始化*/};/*init*/初始化constmaxn=1001;64初始化constmaxn=1001;通过动态规划计算和输出最多可能访问的顶点数procmake;vari,j,k:integer;{fori←1tondo/*枚举每一对顶点*/forj←1tondo{if(i=1)and(j=1)thencontinue;/*若i和j同为出发点，则枚举下一对顶点*/if(i>j)or(i=n)and(j=n)/*计算第一种情况*/then{fork←1tob[i]do/*枚举i的每个前驱顶点，计算经由前驱顶点到达顶点i和到达顶点j的最佳方案*/ifg[i,k]<ithenf[i,j]←max(f[i,j],f[g[i,k],j]+1);continue};/*继续枚举下一对顶点*/ifi<j/*计算第二种情况：枚举j的每个前驱顶点，计算到达顶点i和经由前驱顶点到达顶点j的最佳方案，从中找出到达顶点i和到达顶点j的最佳方案*/then{fork←1tob[j]doifg[j,k]<jthenf[i,j]←max(f[i,j],f[i,g[j,k]]+1);continue};/*继续枚举下一对顶点*/};/*for*/writeln(f[n,n]-2);/*输出最多可能访问的顶点数*/};/*make*/通过动态规划计算和输出最多可能访问的顶点数procmake65通过动态规划计算和输出最多可能访问的顶点数procmake

对于一些阶段性明显、但不具备最优子结构特征的问题，可以考虑将指标函数值当作“状态”，计算每一个可能的状态是否可达，从而变最优化问题为能否到达指定状态的判定性问题。再借用动态规划思想，用递推方式计算最佳值（即按照状态值递增的顺序寻找第一个可达的状态）。计算一些阶段性明显、但不具备最优子结构特征的路径问题对于一些阶段性明显、但不具备最优子结构特征的问题66对于一些阶段性明显、但不具备最优子结构特征的问题例题mod4最优路径问题

在上图中找出从第1点到第4点的一条路径，要求路径长度mod4的余数最小。例题mod4最优路径问题67例题mod4最优路径问题例题mod4最优路径问题该问题最优子结构特征例如一条最优路径（3+2+3）mod4=0。在它走到第2点的、第3点的路径长度mod4的余数不一定是最小：3mod4>0mod4(3+2)mod4>(3+1)mod4。但是我们可以把它转换成判定性问题，用递推法来解决。该问题最优子结构特征例如一条最优路径（3+2+3）mod468该问题最优子结构特征例如一条最优路径（3+2+3）mod4设fk(sk)——从第1点到第k点的长度mod4为sk的路径是否存在的标志。显然（边界条件）（这里lenk,i表示从第k-1点到第k点之间的第i条边的长度）最后的结果就是可以使f4(s4)值为真的最小的s4值。设（这里lenk,i表示从第k-1点到第k点之间的第i条边的69设（这里lenk,i表示从第k-1点到第k点之间的第i条边的fillchar(f，sizeof(f)，false)；/*f清零*/f[1，0]←true；/*边界条件*/fork←2tondo/*阶段：逐条边延伸*/fors←0to3do/*状态：当前路径长度对4的余数*/foru←1tok-1点出发的边数do/*决策：枚举k-1点出发的每一条边*/f[k，s]←f[k，s]orf[k-1，($10000+s-k-1点出发的第u条边的长度)mod4]；/*加上$10000是为防止出现负数*/fori←0to3doiff[n,i]thenbreak；/*搜索最小余数*/输出i；fillchar(f，sizeof(f)，false)；70fillchar(f，sizeof(f)，false)；01背包问题的讨论原始问题：已知背包总容量和k个物件的体积和价值。物件要末装入背包要末不装入。求价值和最大的装入方案。一般方法：阶段i：按照递增顺序枚举物件数i；状态j:在不超过背包总容量的前提下枚举前i件物件的可能体积j;决策：要使得价值和最大，第i个物件装还是不装

01背包问题的讨论原始问题：已知背包总容量和k个物件的体积和7101背包问题的讨论原始问题：已知背包总容量和k个物件的体积和开心的金明

金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N元钱就行”。今天一早金明就开始做预算，但是他想买的东西太多了，肯定会超过妈妈限定的N元。于是，他把每件物品规定了一个重要度，分为5等：用整数1~5表示，第5等最重要。他还从因特网上查到了每件物品的价格（都是整数元）。他希望在不超过N元（可以等于N元）的前提下，使每件物品的价格与重要度的乘积的总和最大。设第j件物品的价格为v[j]，重要度为w[j]，共选中了k件物品，编号依次为j1，j2，……，jk，则所求的总和为：v[j1]*w[j1]+v[j2]*w[j2]+…+v[jk]*w[jk]。（其中*为乘号）请你帮助金明设计一个满足要求的购物单。【输入】第1行，为两个正整数，用一个空格隔开：Nm（其中N（<30000）表示总钱数，m（<25）为希望购买物品的个数）从第2行到第m+1行，第j行给出了编号为j-1的物品的基本数据，每行有2个非负整数vp（其中v表示该物品的价格(v≤10000)，p表示该物品的重要度(1~5)）【输出】只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（<100000000）。开心的金明

金明今天很开心，家里购置的新房就要领钥匙了，新房72开心的金明

金明今天很开心，家里购置的新房就要领钥匙了，新房题目大意给出一个总费用和N件物品，求出在总费用限制下，购买物品使得费用*重要度总和最大。算法如果将总费用作为背包容量，每个物品的价格作为物件体积，则本题可转化为经典的01背包问题。设物品i的价格为v[i]，重要度为p[i]；f[j]表示使用j元可以购买的价格*重要度的最大值。显然，初始时f清零。题目大意给出一个总费用和N件物品，求出在总费用限制下，购73题目大意给出一个总费用和N件物品，求出在总费用限制下，购状态转移方程假设考虑前i-1物品时使用了j元，有两种可能性不购买物品i：此时价格*重要度的最大值依然为f[j]；购买物品i：此时前i-1物品的花费为j-v[i]，价格*重要度的最大值为f[j-v[i]],新增物品i的价值为v[i]*p[i]显然，应该从两种方案里找出一个最佳的：f[j]=max(f[j],f[j-v[i]]+v[i]*p[i])状态转移方程假设考虑前i-1物品时使用了j元，有两种可能74状态转移方程假设考虑前i-1物品时使用了j元，有两种可能实现方法阶段i：依次考虑每一个物品（1≤i≤n）状态j:购买前i种物品的可能钱数。注意，按照递减顺序枚举(j=m…v[i]），因为花费j-v[i]的购买方案是子问题（前i-1种物品的购买方案）。决策：从不购买物品i和购买物品i中选择最优方案f[j]=max(f[j],f[j-v[i]]+v[i]*p[i])实现方法阶段i：依次考虑每一个物品（1≤i≤n）75实现方法阶段i：依次考虑每一个物品（1≤i≤n）实现方法阶段数据结构constmaxv=30000;maxn=25;varv,p:array[1..maxn]oflongint;/*物品i的价格为v[i]，重要度为p[i]*/f:array[0..maxv]oflongint;/*f[i]表示使用i元可以购买的价格*重要度的最大值*/totv,n,ans:longint;/*总钱数为totv,希望购买的物品数为n,不超过总钱数的物品价格与重要度乘积的总和的最大值为ans*/数据结构constmaxv=30000;maxn=25;76数据结构constmaxv=30000;maxn=25;数计算不超过总钱数totv的物品价格与重要度乘积的最大总和fillchar(f,sizeof(f),0);/*状态转移方程初始化*/fori←

1tondo/*枚举每一个物品*/forj←totvdowntov[i]do/*按照递减方向枚举购买前i种物品的所有可能钱数，计算物品价格与重要度乘积的最大总和*/

f[j]←

max(f[j],f[j-v[i]]+v[i]*p[i]);ans←f[totv]/*不超过总钱数totv的物品价格与重要度乘积的最大总和为问题解*/writeln(ans);计算不超过总钱数totv的物品价格与重要度乘积的最大总和fi77计算不超过总钱数totv的物品价格与重要度乘积的最大总和fi最佳子序列问题1、子序列的左右端取数问题2、圆排列的活动方案计数3、计算递增子序列4、计算数和最大的子序列或矩阵5、序列（一维子序列和圆排列）的划分最佳子序列问题1、子序列的左右端取数问题78最佳子序列问题1、子序列的左右端取数问题最佳子序列问题1、子子序列的左右端取数问题设f[i,j]为取子序列g[i,j]的最优解。决策有两个左端取数：f[i+1,j]+g[i]右端取数：f[i,j-1]+g[j]显然f[i,i]=g[i]*取1个数的价值f[i,j]=max{f[i+1,j]+g[i],f[i,j-1]+g[j]}*取1个数的价值阶段l:子序列长度（2≤l≤n）状态i：子序列首指针（1≤i≤n-l+1），子序列尾指针j=i+l-1决策：取i位置的数还是j位置的数

子序列的左右端取数问题设f[i,j]为取子序列g[i,j]的79子序列的左右端取数问题设f[i,j]为取子序列g[i,j]的矩阵取数游戏【问题描述】帅帅经常跟同学玩一个矩阵取数游戏：对于一个给定的n*m的矩阵，矩阵中的每个aij均为非负整数。游戏规则如下：l每次取数时须从每行各取走一个元素，共n个。m次后取完矩阵所有元素；2每次取走的各个元素只能是该元素所在行的行首或行尾；3每次取数都有一个得分值，为每行取数的得分之和，每行取数的得分=被取走的元素值*2i，其中i表示第i次取数(从l开始编号)；4游戏结束总得分为m次取数得分之和。帅帅想请你帮忙写一个程序，对于任意矩阵，可以求出取数后的最大得分。【输入】输入文件qame．in包括n+1行：第l行为两个用空格隔开的整数m和m;第2-n+l行为n*m矩阵，其中每行有m个用单个空格隔开的非负整数。【输出】输出文件game．out仅包含1行，为一个整数，即输入矩阵取数后的最大得分。矩阵取数游戏【问题描述】帅帅经常跟同学玩一个矩阵取数游戏：对80矩阵取数游戏【问题描述】帅帅经常跟同学玩一个矩阵取数游戏：对试题简述给出一个N*M的矩阵，每次取每行的行首和行末的一个数，得分=被取走的元素值*2i（i表示第i次取数）。求最大得分。试题简述给出一个N*M的矩阵，每次取每行的行首和行末的一个数81试题简述给出一个N*M的矩阵，每次取每行的行首和行末的一个数状态转移方程对每行分别进行动态规划，求最大得分。子序列长度作为阶段，首指针作为状态。设F[i,j]表示当前从某行的第