中华中学动态规划讲义.pptx

中中华中学中学动态规划划讲义周默介介绍动态规划是NOIP中非常重要的一类题型。在动态规划中，算法是最难想到的，当你想到了算法，实现也就迎刃而解。今天，我们将强调算法的研究，不作上机实践递推推递推是动态规划的根本，我们首先花一点时间进行递推训练 递推关系是一种简洁高效的常见数学模型，递推关系是一种简洁高效的常见数学模型，递推关系是一种简洁高效的常见数学模型，递推关系是一种简洁高效的常见数学模型，比如我们熟悉的比如我们熟悉的比如我们熟悉的比如我们熟悉的FibonacciFibonacciFibonacciFibonacci数列问题。在这种类数列问题。在这种类数列问题。在这种类数列问题。在这种类型的问题中，每个数据项都和它前面的若干个型的问题中，每个数据项都和它前面的若干个型的问题中，每个数据项都和它前面的若干个型的问题中，每个数据项都和它前面的若干个数据项（或后面的若干个数据项）有一定的关数据项（或后面的若干个数据项）有一定的关数据项（或后面的若干个数据项）有一定的关数据项（或后面的若干个数据项）有一定的关联，这种关联一般是通过一个联，这种关联一般是通过一个联，这种关联一般是通过一个联，这种关联一般是通过一个“递推关系式递推关系式递推关系式递推关系式”来表示的。求解问题时我们从初始的一个或若来表示的。求解问题时我们从初始的一个或若来表示的。求解问题时我们从初始的一个或若来表示的。求解问题时我们从初始的一个或若干个数据项出发，通过递推关系逐步推进，从干个数据项出发，通过递推关系逐步推进，从干个数据项出发，通过递推关系逐步推进，从干个数据项出发，通过递推关系逐步推进，从而得到最终结果，这种求解问题的方法叫而得到最终结果，这种求解问题的方法叫而得到最终结果，这种求解问题的方法叫而得到最终结果，这种求解问题的方法叫“递递递递推法推法推法推法”。其中，初始的若干数据项称为。其中，初始的若干数据项称为。其中，初始的若干数据项称为。其中，初始的若干数据项称为“边界边界边界边界”。解决递推问题有三个重点：解决递推问题有三个重点：一、如何建立正确的递推关系一、如何建立正确的递推关系二、递推关系有何性质二、递推关系有何性质三、递推关系式如何求解三、递推关系式如何求解递推按照我们推导问题的方向，常分为顺推法和递推按照我们推导问题的方向，常分为顺推法和倒推法。倒推法。例例1、有一只经过训练的蜜蜂只能爬向右侧相邻的、有一只经过训练的蜜蜂只能爬向右侧相邻的蜂房，不能反向爬行。试求出蜜蜂从蜂房蜂房，不能反向爬行。试求出蜜蜂从蜂房a爬到蜂爬到蜂房房b的可能路线数。的可能路线数。问题分析：这是一道很典型的问题分析：这是一道很典型的Fibonacci数列类题目，其中的递推关系很明显。由于数列类题目，其中的递推关系很明显。由于“蜜蜂只能爬向右侧相邻的蜂房，不能反向蜜蜂只能爬向右侧相邻的蜂房，不能反向爬爬行行”的限制，决定了蜜蜂到的限制，决定了蜜蜂到b点的路径只能是点的路径只能是从从b-1点或点或b-2点到达的，故点到达的，故fn=fn-1+fn-2(a+2=n=b)，边界条件，边界条件fa=1，fa+1=1。例例2 2、打印杨晖三角形的前、打印杨晖三角形的前1010行。杨晖三角形的行。杨晖三角形的前前5 5行如左下图所示。行如左下图所示。问题分析：我们观察左上图不太容易找问题分析：我们观察左上图不太容易找到规律，但如果将左上图转化为右上图就不难到规律，但如果将左上图转化为右上图就不难发现杨辉三角形其实就是一个二维表（数组）发现杨辉三角形其实就是一个二维表（数组）的下三角部分。的下三角部分。假设用二维数组假设用二维数组yhyh存储，每行首尾元素都为存储，每行首尾元素都为1 1，且，且其中任意一个非首尾元素其中任意一个非首尾元素yhi,jyhi,j的值其实就是的值其实就是yhi-1,j-1yhi-1,j-1与与yhi-1,jyhi-1,j的和，另外每一行的的和，另外每一行的元素个数刚好等于行数。有了这些规律，给数元素个数刚好等于行数。有了这些规律，给数组元素赋值就不难了，而要打印杨晖三角形，组元素赋值就不难了，而要打印杨晖三角形，只需控制一下每行输出的起始位置即可。只需控制一下每行输出的起始位置即可。例例3 3、猴子第、猴子第1 1天摘下若干个桃子天摘下若干个桃子,当即吃了一半又当即吃了一半又一个。第一个。第2 2天又把剩下的桃吃了一半又一个天又把剩下的桃吃了一半又一个,以后以后每天都吃前一天剩下的桃子的一半又一个每天都吃前一天剩下的桃子的一半又一个,到第到第1010天猴子想吃时天猴子想吃时,只剩下一个桃子。只剩下一个桃子。问猴子第问猴子第1 1天一天一共摘了多少桃子共摘了多少桃子?问题分析：问题分析：已知条件第已知条件第 10 10 天剩下天剩下 1 1 个桃子，隐含个桃子，隐含条件每一次前一天的桃子个数等于后一天桃子的条件每一次前一天的桃子个数等于后一天桃子的个数加个数加 1 1 的的 2 2 倍。倍。我们采取逆向思维的方法我们采取逆向思维的方法,从后往前推，从后往前推，可用倒推法求解。可用倒推法求解。VarVar S,I:LongInt;S,I:LongInt;BeginBegin S:=1;S:=1;第第1010天只有一个桃子天只有一个桃子 For I:=9 DownTo 1 Do For I:=9 DownTo 1 Do S:=(S+1)*2;S:=(S+1)*2;第第1010天依次求前一天的桃天依次求前一天的桃 Writeln(S);Writeln(S);子数子数 End.End.程序填空：设有一个程序填空：设有一个n n级的楼梯级的楼梯(1=n=12),(1=n=12),编号编号从下到上依次为从下到上依次为1 1至至n,n,其中有若干级为坏的。有其中有若干级为坏的。有一个人上楼梯时一步可走一个人上楼梯时一步可走1 1级、或级、或2 2级、或级、或3 3级级(坏坏级只能跨过不能踏上级只能跨过不能踏上,但级数照算但级数照算)。问。问:这个人这个人从楼下走到第从楼下走到第n n级级,共有多少种不同的走法共有多少种不同的走法?例如例如:当当n=ln=l时时(无坏级情况下无坏级情况下),),仅有仅有1 1种走法种走法n=2n=2时时(无坏级情况下无坏级情况下),),有有:1:1级级+l+l级级 或或 2 2级级 共共2 2种种走法走法n=3n=3时时(第二级为坏级情况下第二级为坏级情况下),),有有:1:1级级+2+2级级,直接直接3 3级级,共共2 2种走法种走法【程序说明程序说明】用递推方法求解。用集合记录坏级。用递推方法求解。用集合记录坏级。var x,i,n,fl,f2,f3,f4:longint;s:set of 0.30;begin readln(n);s:=readln(x);x:坏级坏级,以以0结束结束 while(xO)do begin s:=readln(x);end;If(1 in s)then f1:=0 else fl:=1;If(2 in s)then f2:=0 else f2:=If(3 in s)then f3:=0 else f3:=1+f1+f2;if n=1 then f4:=f1 else if n=2 then f4:=f2 else if n=3 then f4:=f3 else begin for i:=4 to n do begin if(i in s)then f4:=0 else f4:=fl:=f2;f2:=f3;f3:=f4;end;end;writeln(f4);readln;end.例例4、棋盘上、棋盘上A点有一个过河卒，需要走到目标点有一个过河卒，需要走到目标B点。点。卒行走的规则：可以向下、或者向右。同时在棋盘卒行走的规则：可以向下、或者向右。同时在棋盘上上C点有一个对方的马，该马所在的点和所有跳跃点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为一步可达的点称为对方马的控制点。因此称之为“马马拦过河卒拦过河卒”。棋盘用坐标表示，。棋盘用坐标表示，A点点(0,0)、B点点(n,m)(n,m为不超过为不超过15的整数的整数)，同样马的位置坐标是，同样马的位置坐标是需要给出的。现在要求你计算出卒从需要给出的。现在要求你计算出卒从A点能够到达点能够到达B点的路径的条数，假设马的位置是固定不动的，并点的路径的条数，假设马的位置是固定不动的，并不是卒走一步马走一步。不是卒走一步马走一步。【样例样例】knight.in knight.out6 6 3 36 分析：本题可用搜索算法，但分析：本题可用搜索算法，但N,M=15就会超时。就会超时。再分析题意会发现：要到达棋盘上的一个点，只能再分析题意会发现：要到达棋盘上的一个点，只能从左边过来或是从上面过来。根据加法原理，到达从左边过来或是从上面过来。根据加法原理，到达某一点的路径数目，就等于到达其相邻的上点和左某一点的路径数目，就等于到达其相邻的上点和左点的路径数目之和，因此我们可以使用逐列（或逐点的路径数目之和，因此我们可以使用逐列（或逐行）递推的方法来求出从起点到终点的路径数目。行）递推的方法来求出从起点到终点的路径数目。障碍点（马的控制点）也完全适用，只要将到达该障碍点（马的控制点）也完全适用，只要将到达该点的路径数目设置为点的路径数目设置为0即可。即可。假设用假设用fi，j表示到达点（表示到达点（i,j）的路径数目，用）的路径数目，用gi,j表示点表示点(i,j)是否是对方马的控制点，是否是对方马的控制点，gi,j=0表示表示不是对方马的控制点，不是对方马的控制点，gi,j=1表示是对方马的控制表示是对方马的控制点。则，我们可以得到如下的递推关系式：点。则，我们可以得到如下的递推关系式：递推边界为递推边界为f0,0=1,f0,0=1,考虑到最大情况下：考虑到最大情况下：n=20,m=20n=20,m=20，路径条数可能会超出长整数范围所以要，路径条数可能会超出长整数范围所以要使用使用CompComp类型或高精度运算。类型或高精度运算。fi,j=0 gx,y=1fi,j=0 gx,y=1fi,0=fi-1,0 i0,gx,y=0fi,0=fi-1,0 i0,gx,y=0f0,j=f0,j-1 j0,gx,y=0f0,j=f0,j-1 j0,gx,y=0fi,j=fi-1,j+fI,j-1 i0,j0,gx,y=0fi,j=fi-1,j+fI,j-1 i0,j0,gx,y=0 例例5 5、(NOIP(NOIP普及组第四题）给定普及组第四题）给定A,B,CA,B,C三根足够长的三根足够长的细柱，在细柱，在A A柱上放有柱上放有2n2n个中间有空的圆盘，共有个中间有空的圆盘，共有n n个不同的尺寸，每个个不同的尺寸，每个尺寸都有两个相同的圆盘，注意这两个圆盘是不加尺寸都有两个相同的圆盘，注意这两个圆盘是不加区分的区分的(下图为下图为n=3n=3的情形）。现要将的情形）。现要将 这些国盘移到这些国盘移到C C柱上，在移动过程中可放在柱上，在移动过程中可放在B B柱上暂存。要求柱上暂存。要求:(1)(1)每次只能移动一个圆盘；每次只能移动一个圆盘；(2)A(2)A、B B、C C三根细柱上的圆盘都要保持上小下大的三根细柱上的圆盘都要保持上小下大的顺序；顺序；任务任务:设设AnAn为为2n2n个圆盘完成上述任务所需的最少移动个圆盘完成上述任务所需的最少移动次数，对于输入的次数，对于输入的n n，输出，输出AnAn。【输入输入】输入文件输入文件hanoi.inhanoi.in为一个正整数为一个正整数n n，表示，表示在在A A柱上放有柱上放有2n2n个圆盘。个圆盘。【输出输出】输出文件输出文件hanoi.outhanoi.out仅一行，包含一个正仅一行，包含一个正整数，为完成上述任务所需的最少移动次数整数，为完成上述任务所需的最少移动次数AnAn。【输入输出样例输入输出样例1 1】hanoi.in hanoi.outhanoi.in hanoi.out1 21 2问题分析：如果每个尺寸只有一个圆盘，共问题分析：如果每个尺寸只有一个圆盘，共n n个个圆盘，也就是常见的汉诺塔问题。则设圆盘，也就是常见的汉诺塔问题。则设h hn n为为n n 个盘子个盘子从从a a柱移到柱移到c c柱所需移动的盘次。显然，当柱所需移动的盘次。显然，当n=1n=1时，只时，只需把需把a a 柱上的盘子直接移动到柱上的盘子直接移动到c c柱就可以了，故柱就可以了，故h h1 1=1=1。当当n=2n=2时，先将时，先将a a柱上面的小盘子移动到柱上面的小盘子移动到b b柱上去；然柱上去；然后将大盘子从后将大盘子从a a柱移到柱移到c c 柱；最后，将柱；最后，将b b柱上的小盘子柱上的小盘子移到移到c c柱上，共记柱上，共记3 3个盘次，故个盘次，故h h2 2=3=3。以此类推，当。以此类推，当a a柱上有柱上有n(n=2)n(n=2)个盘子时，总是先借助个盘子时，总是先借助c c柱把上面的柱把上面的n-n-1 1个盘子移动到个盘子移动到b b柱上，然后把柱上，然后把a a柱最下面的盘子移动柱最下面的盘子移动到到c c柱上；再借助柱上；再借助a a柱把柱把b b柱上的柱上的n-1n-1个盘子移动到个盘子移动到c c柱柱上；总共移动上；总共移动h hn-1n-1+1+h+1+hn-1n-1个盘次。个盘次。h hn n=2h=2hn-1n-1+1 +1 边界条件：边界条件：h hn-1n-1=1=1该题若仔细观察，很容易发现是该题若仔细观察，很容易发现是hanoi塔的变形塔的变形（只不过多了几个盘子），操作过程中，可以（只不过多了几个盘子），操作过程中，可以将两个相同尺寸的盘子看成一个整体，这样就将两个相同尺寸的盘子看成一个整体，这样就成了典型的成了典型的hanoi塔问题。再运用公式：塔问题。再运用公式：fn=2n-1来做，最后只要乘来做，最后只要乘2就行了。由于数据就行了。由于数据较大，须用到高精度运算。较大，须用到高精度运算。题型大型大类简单线性dp背包最长XX子序列最长公共子序列LCS区间dp树dp坐标dp。1.数塔数塔738810277455265如图，有一数字三角形。数字三角形中的数字为不超过100的正整数。数字三角形中的数字为不超过100的正整数。现规定从最顶层走到最底层，每一步可沿左斜线向下或右斜线向下走。假设三角形行数100，编程求解从最顶层走到最底层的一条路径，使得沿着该路径所经过的数字的总和最大，输出最大值。此数塔输出为30是否可以用前两次课所用的深搜呢。显然前两次课的深搜写数塔这道题的时候程序简明易懂。但是当行数很大时，当三角形的行数等于100时，其枚举量之大是可想而知的，用枚举法肯定超时，甚至根本不能得到计算结果，必须用动态规划法来解。constmaxn=10;vara:array1.maxn,1.maxnofinteger;max:longint;n,i,j:integer;proceduretry(x,y,dep:integer;sum:longint);beginif(dep=n)thenbeginifsummaxthenmax:=sum;exitend;try(x+1,y,dep+1,sum+ax+1,y);try(x+1,y+1,dep+1,sum+ax+1,y+1);end;beginreadln(n);fori:=1tondoforj:=1toidoread(ai,j);max:=0;try(1,1,1,a1,1);writeln(max);end.那我们又该如何实现动态规划呢？1.逆推法:按三角形的行划分阶段，若行数为n，则可把问题看做一个n-1个阶段的决策问题。先求出第n-1阶段(第n-1行上各点)到第n行的的最大和，再依次求出第n-2阶段、第n-3阶段第1阶段(起始点)各决策点至第n行的最佳路径。设：fi,j为从第i阶段中的点j至第n行的最大的数字和；则:fn,j=an,j1=j=nfi,j=maxai,j+fi+1,j,ai,j+fi+1,j+11=jfi+1,j+1 then fi,j:=ai,j+fi+1,j else fi,j:=ai,j+fi+1,j+1;writeln(f1,1);end.2.顺推法按三角形的行划分阶段，若行数为n，则可把问题看做一个n-1个阶段的决策问题。先求第2行各元素到起点的最大和,再依次求出第3,4，5,.,.n-1,n到起点的最大和,最后找第n行的最大值设fi,j为第i行第j列上点到起点的最大和则f1，1=a1,1;fi，1=ai,1+fi-1,1;fi，j=maxai,j+fi-1,j-1,ai,j+fi-1,j2=jfi-1,j then fi,j:=ai,j+fi-1,j-1 else fi,j:=ai,j+fi-1,j;end;maxsum:=0;for i:=1 to n do if fn,imaxsum then maxsum:=fn,i;writeln(maxsum);end.2.最最长不下降子序列不下降子序列设有由n个不相同的整数组成的数列，记为:a(1)、a(2)、a(n)例如3，18，7，14，10，12，23，41，16，24。若存在i1i2i3ie且有a(i1)a(i2)a(ie)则称为长度为e的不下降序列。如上例中3，18，23，24就是一个长度为4的不下降序列，同时也有3，7，10，12，16，24长度为6的不下降序列。程序要求，当原数列给出之后，求出最长的不下降序列。const maxn=100;var a,b,c:array1.maxn of integer;n,i,j,max,p:integer;begin readln(n);for i:=1 to n do begin read(ai);bn:=1;cn:=0;end;for i:=n-1 downto 1 do begin max:=0;p:=0;for j:=i+1 to n do if(aimax)then begin max:=bj;p:=j end;if p0 then begin bi:=bp+1;ci:=p end end;max:=0;p:=0;for i:=1 to n do if bimax then begin max:=bi;p:=i end;writeln(maxlong=,max);while p0 do begin write(ap:5);p:=cp end;end.谁能够说出刚刚做法的时间复杂度？n2有没有速度更快的做法呢有！下面介绍nlogn的算法varn,i,ans,j,k,m:longint;a,b:array1.10000oflongint;beginread(n);fori:=1tondoread(ai);ans:=0;fori:=1tondobeginj:=1;k:=ans;whilej=kdobeginm:=(j+k)div2;ifbmanstheninc(ans);bj:=ai;end;writeln(ans);end.同样的道理我们也可以做最长不上升子序列等等最长XX子序列3.背包背包问题1.部分背包问题一个旅行者有一个最多能用m公斤的背包，现在有n种物品，它们的总重量分别是W1，W2，.,Wn,它们的总价值分别为C1,C2,.,Cn.求旅行者能获得最大总价值。解决问题的方法是贪心算法:将C1/W1,C2/W2,.Cn/Wn,从大到小排序,不停地选择价值与重量比最大的放人背包直到放满为止.2.0/1背包一个旅行者有一个最多能用m公斤的背包，现在有n件物品，它们的重量分别是W1，W2，.,Wn,它们的价值分别为C1,C2,.,Cn.若每种物品只有一件求旅行者能获得最大总价值。分析说明:显然这个题可用深度优先方法对每件物品进行枚举(选或不选用0,1控制).程序简单,但是当n的值很大的时候不能满足时间要求，时间复杂度为O（2n）。按递归的思想我们可以把问题分解为子问题,使用递归函数设f(i，x)表示前i件物品，总重量不超过x的最优价值则f（i，x）=max(f(i1，x-Wi)+Ci，f（i1，x）f（n，m）即为最优解，边界条件为f（0，x）0，f(i,0)=0;const maxm=200;maxn=30;type ar=array1.maxn of integer;var m,n,j,i:integer;c,w:ar;f:array0.maxn,0.maxm of integer;function max(x,y:integer):integer;begin if xy then max:=x else max:=y;end;begin readln(m,n);for i:=1 to n do readln(wi,ci);for i:=1 to m do f(0,i):=0;for i:=1 to n do f(i,0):=0;for i:=1 to n do for j:=1 to m do begin if j=wi then fi,j:=max(fi-1,j-wi+ci,fi-1,j)else fi,j:=fi-1,j;end;writeln(fn,m);end.3.完全背包问题一个旅行者有一个最多能用m公斤的背包，现在有n种物品，每件的重量分别是W1，W2，.,Wn,每件的价值分别为C1,C2,.,Cn.若的每种物品的件数足够多.求旅行者能获得的最大总价值。本问题的数学模型如下：设f(x)表示重量不超过x公斤的最大价值，则f(x）=maxf(x-wi)+ci当x=wi1=i=n思考：我们该如何把01背包改成完全背包呢？4.采采药辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”如果你是辰辰，你能完成这个任务吗？4.采采药【输入文件】输入文件medic.in的第一行有两个整数T（1=T=1000）和M（1=M=100），用一个空格隔开，T代表总共能够用来采药的时间，M代表山洞里的草药的数目。接下来的M行每行包括两个在1到100之间（包括1和100）的整数，分别表示采摘某株草药的时间和这株草药的价值。【输出文件】输出文件medic.out包括一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。【样例输入】7037110069112【样例输出】3【数据规模】对于30%的数据，M=10；对于全部的数据，M=100。5.开心的金明开心的金明金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N元钱就行”。今天一早金明就开始做预算，但是他想买的东西太多了，肯定会超过妈妈限定的N元。于是，他把每件物品规定了一个重要度，分为5等：用整数15表示，第5等最重要。他还从因特网上查到了每件物品的价格（都是整数元）。他希望在不超过N元（可以等于N元）的前提下，使每件物品的价格与重要度的乘积的总和最大。设第j件物品的价格为vj，重要度为wj，共选中了k件物品，编号依次为j1，j2，jk，则所求的总和为：vj1*wj1+vj2*wj2+vjk*wjk。（其中*为乘号）请你帮助金明设计一个满足要求的购物单。5.开心的金明开心的金明【输入文件】输入文件happy.in的第1行，为两个正整数，用一个空格隔开：Nm（其中N（30000）表示总钱数，m（25）为希望购买物品的个数。）从第2行到第m+1行，第j行给出了编号为j-1的物品的基本数据，每行有2个非负整数vp（其中v表示该物品的价格(v=10000)，p表示该物品的重要度(15)）【输出文件】输出文件happy.out只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（100000000）。【输入样例】1000580024005300540032002【输出样例】39006.金明的金明的预算方案算方案金明今天很开心，家里购置的新房就要领钥匙了，新房里金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间金明自己专用的很宽敞的房间。更让他高兴的是，有一间金明自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：妈妈昨天对他说：“你的房间需要购买哪些物品，怎么你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过布置，你说了算，只要不超过N元钱就行元钱就行”。今天一早，。今天一早，金明就开始做预算了，他把想买的物品分为两类：主件金明就开始做预算了，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的，下表就是一些主件与附件，附件是从属于某个主件的，下表就是一些主件与附件的例子：主件与附件的例子：主件 附件电脑附件电脑 打印机，扫描仪书柜打印机，扫描仪书柜 图图书书桌书书桌 台灯，文具工作椅台灯，文具工作椅 无如果要买归类为附件无如果要买归类为附件的物品，必须先买该附件所属的主件。每个主件可以有的物品，必须先买该附件所属的主件。每个主件可以有0个、个、1个或个或2个附件。附件不再有从属于自己的附件。个附件。附件不再有从属于自己的附件。金明想买的东西很多，肯定会超过妈妈限定的金明想买的东西很多，肯定会超过妈妈限定的N元。于元。于是，他把每件物品规定了一个重要度，分为是，他把每件物品规定了一个重要度，分为5等：用整等：用整数数15表示，第表示，第5等最重要。他还从因特网上查到了每件等最重要。他还从因特网上查到了每件物品的价格（都是物品的价格（都是10元的整数倍）。他希望在不超过元的整数倍）。他希望在不超过N元（可以等于元（可以等于N元）的前提下，使每件物品的价格与重元）的前提下，使每件物品的价格与重要度的乘积的总和最大。设第要度的乘积的总和最大。设第j件物品的价格为件物品的价格为vj，重要度为，重要度为wj，共选中了，共选中了k件物品，编号依次为件物品，编号依次为j1，j2，jk，则所求的总和为：，则所求的总和为：vj1*wj1+vj2*wj2+vjk*wjk。（其中。（其中*为乘号）请你帮助金明设计一为乘号）请你帮助金明设计一个满足要求的购物单。个满足要求的购物单。6.金明的金明的预算方案算方案【输入文件输入文件】输入文件的第输入文件的第1行，为两个正整数，用行，为两个正整数，用一个空格隔开：一个空格隔开：N m 其中其中N（32000）表示总钱数，）表示总钱数，m（60）为希望购买物品的个数。）为希望购买物品的个数。）从第从第2行到行到第第m+1行，第行，第j行给出了编号为行给出了编号为j-1的物品的基本数据，每的物品的基本数据，每行有行有3个非负整数个非负整数 v p q（其中（其中v表示该物品的价格表示该物品的价格（v0，表示该物品为附件，表示该物品为附件，q是所属主件的编号）是所属主件的编号）【输出文件输出文件】输出文件只有一个正整数，为不超过总钱数输出文件只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值的物品的价格与重要度乘积的总和的最大值（=ai,0)and(fi,j=(ai,0+ai,1)and(fi,j=(ai,0+ai,2)and(fi,j=(ai,0+ai,1+ai,2)and(fi,jdi,j-1 then di,j:=di-1,j else di,j:=di,j-1;end;下面我们给出一个基本的程序段8.回文回文词【题目描述】（vijos1327）回文词是一种对称的字符串也就是说，一个回文词，从左到右读和从右到左读得到的结果是一样的。任意给定一个字符串，通过插入若干字符，都可以变成一个回文词。你的任务是写一个程序，求出将给定字符串变成回文词所需插入的最少字符数。比如字符串“Ab3bd”，在插入两个字符后可以变成一个回文词（“dAb3bAd”或“Adb3bdA”）。然而，插入两个以下的字符无法使它变成一个回文词。【输入格式】第一行包含一个整数N，表示给定字符串的长度，3=Nythenexit(x)elseexit(y);end;Beginreadln(n);fori:=1tondobeginread(ai);bn-i+1:=ai;/制作S2end;fori:=1tondo/LCSforj:=1tondoifai=bjthenfi,j:=fi-1,j-1+1elsefi,j:=max(fi-1,j,fi,j-1);writeln(n-fn,n);/输出需要配对的字符数end.思考题：如果是3个字符串求最长公共子序列又该怎么做呢？9.区区间dp合并：意思就是将两个或多个部分进行整合并：意思就是将两个或多个部分进行整合，当然也可以反过来，也就是是将一个合，当然也可以反过来，也就是是将一个问题进行分解成两个或多个部分。问题进行分解成两个或多个部分。特征：能将问题分解成为两两合并的形式特征：能将问题分解成为两两合并的形式求解：对整个问题设最优值，枚举合并点，求解：对整个问题设最优值，枚举合并点，将问题分解成为左右两个部分，最后将左将问题分解成为左右两个部分，最后将左右两个部分的最优值进行合并得到原问题右两个部分的最优值进行合并得到原问题的最优值。有点类似分治算法的解题思想。的最优值。有点类似分治算法的解题思想。典型试题：整数划分，凸多边形划分、石典型试题：整数划分，凸多边形划分、石子合并、多边形合并、能量项链等。子合并、多边形合并、能量项链等。10.整数划分整数划分给出一个长度为给出一个长度为n的数的数要在其中加要在其中加m-1个乘号，分成个乘号，分成m段段这这m段的乘积之和最大段的乘积之和最大mn=20有有T组数据，组数据，T=1000010.整数划分整数划分给出一个长度为给出一个长度为n的数的数要在其中加要在其中加m-1个乘号，分成个乘号，分成m段段这这m段的乘积之和最大段的乘积之和最大mn=20有有T组数据，组数据，T=1000010.整数划分整数划分可以先预处理出原数第可以先预处理出原数第i到到j段的数值段的数值Ai,j是是多少，这样转移就方便了，预处理也要尽多少，这样转移就方便了，预处理也要尽量降低复杂度。量降低复杂度。Fi，j表示把这个数前表示把这个数前i位分成位分成j段得到的最段得到的最大乘积。大乘积。Fi,j=Fk,j-1*Ak+1,i,1ki=n,j2,maxint*500);readln(n);fori:=1tondobeginread(mapi);mapi+n:=mapi;end;fori:=1to2*ndobeginfi,i:=0;gi,i:=0;end;end;functionsum(a,b:longint):longint;vari:longint;beginsum:=0;fori:=atobdoinc(sum,mapi);exit(sum);end;functionmax(a,b:longint):longint;beginifabthenexit(a)elseexit(b);end;functionmin(a,b:longint):longint;beginifaansthenans:=fi,i+n-1;ifgi,i+n-1ans1thenans1:=gi,i+n-1;end;writeln(ans1);writeln(ans);end;begininit;dp;end.12.最大正方形最大正方形NaGG的院子是一个NN的网格，每颗杂草最多占据一个11的网格。由于时间紧迫，他已经来不及清理所有杂草，所以只希望能够找出一个最大的正方形区域，在这个区域内没有杂草。样例输入样例输入2-1000样例输出样例输出1此类dp我们一般称之为坐标dp，如本题则是在一个二维坐标系中找一个最大的正方形。这样的题如何写转移方程？f(i,j)=minf(i-1,j-1),f(i-1,j),f(i,j-1)+1为什么是这样？大家自己画图看一看!解析：解析：Gi+1j,Gij+1,Gi+1j,Gij+1,Gi+1j+1Gi+1j+1分别为分别为(i,j)i,j)向下、向右、向右下向下、向右、向右下一格的状况。在一格的状况。在(n-1,n-1)n-1,n-1)当且仅当三者都为当且仅当三者都为1 1的时候，正方形才能扩充。从最右下向上，依的时候，正方形才能扩充。从最右下向上，依次扩充即可。次扩充即可。13.能量能量项链在Mars星球上，每个Mars人都随身佩带着一串能量项链。在项链上有N颗能量珠。能量珠是一颗有头标记与尾标记的珠子，这些标记对应着某个正整数。并且，对于相邻的两颗珠子，前一颗珠子的尾标记一定等于后一颗珠子的头标记。因为只有这样，通过吸盘（吸盘是Mars人吸收能量的一种器官）的作用，这两颗珠子才能聚合成一颗珠子，同时释放出可以被吸盘吸收的能量。如果前一颗能量珠的头标记为m，尾标记为r，后一颗能量珠的头标记为r，尾标记为n，则聚合后释放的能量为m*r*n（Mars单位），新产生的珠子的头标记为m，尾标记为n。需要时，Mars人就用吸盘夹住相邻的两颗珠子，通过聚合得到能量，直到项链上只剩下一颗珠子为止。显然，不同的聚合顺序得到的总能量是不同的，请你设计一个聚合顺序，使一串项链释放出的总能量最大。例如：设N=4，4颗珠子的头标记与尾标记依次为(2，3)(3，5)(5，10)(10，2)。我们用记号表示两颗珠子的聚合操作，(jk)表示第j，k两颗珠子聚合后所释放的能量。则第4、1两颗珠子聚合后释放的能量为：(41)=10*2*3=60。这一串项链可以得到最优值的一个聚合顺序所释放的总能量为(41)2)3）=10*2*3+10*3*5+10*5*10=710。13.能量能量项链输入格式输入格式输入文件的第一行是一个正整数N（4N100），表示项链上珠子的个数。第二行是N个用空格隔开的正整数，所有的数均不超过1000。第i个数为第i颗珠子的头标记（1iN），当1iN时，第i颗珠子的尾标记应该等于第i+1颗珠子的头标记。第N颗珠子的尾标记应该等于第1颗珠子的头标记。至于珠子的顺序，你可以这样确定：将项链放到桌面上，不要出现交叉，随意指定第一颗珠子，然后按顺时针方向确定其他珠子的顺序。输出格式输出格式输出文件只有一行，是一个正整数E（E2.1*109），为一个最优聚合顺序所释放的总能量。样例输入样例输入423510样例输出样例输出71013.能量能量项链和前面那一道题有相似之处?石子合并动态转移方程fi,j=maxfi,k+fk+1,j+pi*pk+1*pj+1(i=kj)谁能解释一下这个动态转移方程的意义fi,k表示第i颗珠子到第k颗珠子此前释放的能量pi*pk+1*pj+1即为本次合并释放的能量同样，这也是一个环形的题目，所以我们和之前一样，将数组扩大一倍，最后选取长度为n且释放能量最大的为答案