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

《中华中学动态规划讲义.ppt》由会员分享，可在线阅读，更多相关《中华中学动态规划讲义.ppt（73页珍藏版）》请在三一文库上搜索。

1、中华中学动态规划讲义,周默,介绍,动态规划是NOIP中非常重要的一类题型。在动态规划中，算法是最难想到的，当你想到了算法，实现也就迎刃而解。今天，我们将强调算法的研究，不作上机实践,递推,递推是动态规划的根本，我们首先花一点时间进行递推训练,递推关系是一种简洁高效的常见数学模型，比如我们熟悉的Fibonacci数列问题。在这种类型的问题中，每个数据项都和它前面的若干个数据项（或后面的若干个数据项）有一定的关联，这种关联一般是通过一个“递推关系式”来表示的。求解问题时我们从初始的一个或若干个数据项出发，通过递推关系逐步推进，从而得到最终结果，这种求解问题的方法叫“递推法”。其中，初始的若干数据项

2、称为“边界”。,解决递推问题有三个重点：,一、如何建立正确的递推关系 二、递推关系有何性质 三、递推关系式如何求解,递推按照我们推导问题的方向，常分为顺推法和倒推法。,例1、有一只经过训练的蜜蜂只能爬向右侧相邻的 蜂房，不能反向爬行。试求出蜜蜂从蜂房a爬到蜂 房b的可能路线数。,问题分析：这是一道很典型的Fibonacci 数列类题目，其中的递推关系很明显。由于 “蜜蜂只能爬向右侧相邻的蜂房，不能反向爬 行”的限制，决定了蜜蜂到b点的路径只能是 从b-1点或b-2点到达的，故fn=fn-1+fn-2 (a+2=n=b)，边界条件fa=1，fa+1=1。,例2、打印杨晖三角形的前10行。杨晖三角

3、形的前5行如左下图所示。,问题分析：我们观察左上图不太容易找到规律，但如果将左上图转化为右上图就不难发现杨辉三角形其实就是一个二维表（数组）的下三角部分。,假设用二维数组yh存储，每行首尾元素都为1，且其中任意一个非首尾元素yhi,j的值其实就是yhi-1,j-1与yhi-1,j的和，另外每一行的元素个数刚好等于行数。有了这些规律，给数组元素赋值就不难了，而要打印杨晖三角形，只需控制一下每行输出的起始位置即可。,例3、猴子第1天摘下若干个桃子,当即吃了一半又一个。第2天又把剩下的桃吃了一半又一个,以后每天都吃前一天剩下的桃子的一半又一个,到第10天猴子想吃时,只剩下一个桃子。 问猴子第1天一共

4、摘了多少桃子?,问题分析： 已知条件第 10 天剩下 1 个桃子，隐含条件每一次前一天的桃子个数等于后一天桃子的个数加 1 的 2 倍。 我们采取逆向思维的方法,从后往前推，可用倒推法求解。,Var S,I:LongInt; Begin S:=1;第10天只有一个桃子 For I:=9 DownTo 1 Do S:=(S+1)*2;第10天依次求前一天的桃 Writeln(S); 子数 End.,程序填空：设有一个n级的楼梯(1=n=12),编号从下到上依次为1至n,其中有若干级为坏的。有一个人上楼梯时一步可走1级、或2级、或3级(坏级只能跨过不能踏上,但级数照算)。问:这个人从楼下走到第n级

5、,共有多少种不同的走法? 例如: 当n=l时(无坏级情况下),仅有1种走法 n=2时(无坏级情况下),有:1级+l级 或 2级 共2种走法 n=3时(第二级为坏级情况下),有:1级+2级,直接3级, 共2种走法 【程序说明】用递推方法求解。用集合记录坏级。,var x,i,n,fl,f2,f3,f4:longint;s:set of 030; 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) t

6、hen 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

7、点有一个对方的马，该马所在的点和所有跳跃 一步可达的点称为对方马的控制点。因此称之为“马 拦过河卒”。棋盘用坐标表示，A点(0, 0)、B点(n, m)(n, m为不超过15的整数)，同样马的位置坐标是 需要给出的。现在要求你计算出卒从A点能够到达B 点的路径的条数，假设马的位置是固定不动的，并 不是卒走一步马走一步。 【样例】 knight.in knight.out 6 6 3 3 6,分析：本题可用搜索算法，但N,M=15就会超时。 再分析题意会发现：要到达棋盘上的一个点，只能 从左边过来或是从上面过来。根据加法原理，到达 某一点的路径数目，就等于到达其相邻的上点和左 点的路径数目之和，

8、因此我们可以使用逐列（或逐 行）递推的方法来求出从起点到终点的路径数目。 障碍点（马的控制点）也完全适用，只要将到达该 点的路径数目设置为0即可。,假设用fi，j表示到达点（i,j）的路径数目，用 gi,j表示点(i,j)是否是对方马的控制点，gi,j=0表示 不是对方马的控制点，gi,j=1表示是对方马的控制 点。则，我们可以得到如下的递推关系式：,递推边界为f0,0=1,考虑到最大情况下： n=20,m=20，路径条数可能会超出长整数范围所以要使用Comp类型或高精度运算。,fi,j=0 gx,y=1 fi,0=fi-1,0 i0,gx,y=0 f0,j=f0,j-1 j0,gx,y=0

9、fi,j=fi-1,j+fI,j-1 i0,j0,gx,y=0,例5、(NOIP普及组第四题）给定A,B,C三根足够长的细柱，在A柱上放有 2n个中间有空的圆盘，共有n个不同的尺寸，每个 尺寸都有两个相同的圆盘，注意这两个圆盘是不加 区分的(下图为n=3的情形）。现要将 这些国盘移到 C柱上，在移动过程中可放在B柱上暂存。要求: (1)每次只能移动一个圆盘； (2) A、B、C三根细柱上的圆盘都要保持上小下大的顺序； 任务:设An为2n个圆盘完成上述任务所需的最少移动次数，对于输入的n，输出An。,【输入】 输入文件hanoi.in为一个正整数n，表示在A柱上放有2n个圆盘。 【输出】 输出文

10、件hanoi.out仅一行，包含一个正整数，为完成上述任务所需的最少移动次数An。 【输入输出样例1】 hanoi.in hanoi.out 1 2,问题分析：如果每个尺寸只有一个圆盘，共n个 圆盘，也就是常见的汉诺塔问题。则设hn为n 个盘子 从a柱移到c柱所需移动的盘次。显然，当n=1时，只 需把a 柱上的盘子直接移动到c柱就可以了，故h1=1。 当n=2时，先将a柱上面的小盘子移动到b柱上去；然 后将大盘子从a柱移到c 柱；最后，将b柱上的小盘子 移到c柱上，共记3个盘次，故h2=3。以此类推，当a 柱上有n(n=2)个盘子时，总是先借助c柱把上面的n- 1个盘子移动到b柱上，然后把a柱

11、最下面的盘子移动 到c柱上；再借助a柱把b柱上的n-1个盘子移动到c柱 上；总共移动hn-1+1+hn-1个盘次。 hn=2hn-1+1 边界条件：hn-1=1,该题若仔细观察，很容易发现是hanoi塔的变形 （只不过多了几个盘子），操作过程中，可以 将两个相同尺寸的盘子看成一个整体，这样就 成了典型的hanoi塔问题。再运用公式： fn=2n-1来做，最后只要乘2就行了。由于数据 较大，须用到高精度运算。,题型大类,简单线性dp 背包 最长XX子序列 最长公共子序列LCS 区间dp 树dp 坐标dp 。,1.数塔,7 3 8 8 1 0 2 7 7 4 5 5 2 6 5 如图，有一数字三角

12、形。数字三角形中的数字为不超过100的正整数。数字三角形中的数字为不超过100的正整数。现规定从最顶层走到最底层，每一步可沿左斜线向下或右斜线向下走。假设三角形行数100，编程求解从最顶层走到最底层的一条路径，使得沿着该路径所经过的数字的总和最大，输出最大值。 此数塔输出为30,是否可以用前两次课所用的深搜呢。显然前两次课的深搜写数塔这道题的时候程序简明易懂。但是当行数很大时，当三角形的行数等于100时，其枚举量之大是可想而知的，用枚举法肯定超时，甚至根本不能得到计算结果，必须用动态规划法来解。 const maxn=10; var a:array1maxn,1maxn of integer;

13、 max:longint;n,i,j:integer; procedure try(x,y,dep:integer;sum:longint); begin if (dep=n) then begin if summax then max:=sum; exit end; try(x+1,y,dep+1,sum+ax+1,y); try(x+1,y+1,dep+1,sum+ax+1,y+1);end; begin readln(n); for i:=1 to n do for j:= 1 to i do read(ai,j); max:=0; try(1,1,1,a1,1); writeln(ma

14、x); end.,那我们又该如何实现动态 规划呢？,1.逆推法: 按三角形的行划分阶段，若行数为 n，则可把问题看做一个n-1个阶段的决策问题。先求出第n-1阶段(第n-1行上各点)到第n行的的最大和，再依次求出第n-2阶段、第n-3阶段第1阶段(起始点)各决策点至第n行的最佳路径。设：fi,j为从第i阶段中的点j至第n行的最大的数字和；则: fn,j=an,j 1=j=n fi,j=maxai,j+fi+1,j,ai,j+fi+1,j+1 1=j=i. f1,1即为所求。,const maxn=100; var n,i,j:integer; a:array1maxn,1maxn of int

15、eger; f:array1maxn,1maxn of integer; begin readln(n); for i:=1 to n do for j:=1 to i do read（ai,j); for i:=1 to n do fn,i:=an,i; for i:=n-1 downto 1 do for j:=1 to i do if fi+1,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个阶段的决策问

16、题。先求第2行各元素到起点的最大和 ,再依次求出第3,4，5,.n-1,n到起点的最大和,最后找第n行的最大值 设fi,j为 第i行第j列上点到起点的最大和 则 f1，1=a1,1; fi，1=ai, 1+fi-1,1; f i，j =max ai,j+fi-1,j-1,ai,j+fi-1,j 2=j=i max(fn,1,fn,2,.,fn,n即为所求。,const maxn=100; var n,i,j:integer; a:array1maxn,1maxn of integer; f:array1maxn,1maxn of integer; maxsum:integer; begin r

17、eadln(n); for i:=1 to n do for j:=1 to i do read(ai,j); fillchar(f,sizeof(f),0); f1,1:=a1,1; for i:=2 to n do begin fi,1:=ai,1+fi-1,1; for j:=2 to i do if fi-1,j-1fi-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)

18、; end.,2.最长不下降子序列,设有由n个不相同的整数组成的数列，记为:a(1)、a(2)、a(n)例如3，18，7，14，10，12，23，41，16，24。若存在i1i2i3 ie 且有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:array1maxn of integer; n,i,j,max,p:integer; begin readln(n); f

19、or 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 beg

20、in write(ap:5);p:=cp end; end.,谁能够说出刚刚做法的时间复杂度？ n2 有没有速度更快的做法呢 有！下面介绍nlogn的算法,var n,i,ans,j,k,m:longint; a,b:array110000 of longint; begin read(n); for i := 1 to n do read(ai); ans:=0; for i := 1 to n do begin j:=1;k:=ans; while j ans then inc(ans); bj:=ai; end; writeln(ans); end.,同样的道理我们也可以做最长不上升子序

21、列等等最长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.若每种物品只有一件求旅行者能获得最大总价值。 分析说明: 显然这个题可用深度优先方法对每件物品进行枚举(选

22、或不选用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=array1maxn of integer; var m,n,j,i:integer; c,w:ar; f:array0maxn,0maxm of integer; function

23、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); e

24、nd.,3.完全背包问题 一个旅行者有一个最多能用m公斤的背包，现在有n种物品，每件的重量分别是W1，W2，.,Wn, 每件的价值分别为C1,C2,.,Cn.若的每种物品的件数足够多. 求旅行者能获得的最大总价值。 本问题的数学模型如下： 设 f(x)表示重量不超过x公斤的最大价值， 则 f(x）=maxf(x-wi)+ci 当x=wi 1=i=n 思考：我们该如何把01背包改成完全背包呢？,4.采药,辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞

25、里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。” 如果你是辰辰，你能完成这个任务吗？,4.采药,【输入文件】输入文件medic.in的第一行有两个整数T（1 = T = 1000）和M（1 = M = 100），用一个空格隔开，T代表总共能够用来采药的时间，M代表山洞里的草药的数目。接下来的M行每行包括两个在1到100之间（包括1和100）的整数，分别表示采摘某株草药的时间和这株草药的价值。 【输出文件】输出文件medic.out包括一行，这一行只包含一个整数，

26、表示在规定的时间内，可以采到的草药的最大总价值。 【样例输入】 70 3 71 100 69 1 1 2 【样例输出】3 【数据规模】对于30%的数据，M = 10；对于全部的数据，M = 100。,5.开心的金明,金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N元钱就行”。今天一早金明就开始做预算，但是他想买的东西太多了，肯定会超过妈妈限定的N元。于是，他把每件物品规定了一个重要度，分为5等：用整数15表示，第5等最重要。他还从因特网上查到了每件物品的价格（都是整数元

27、）。他希望在不超过N元（可以等于N元）的前提下，使每件物品的价格与重要度的乘积的总和最大。 设第j件物品的价格为vj，重要度为wj，共选中了k件物品，编号依次为j1，j2，jk，则所求的总和为： vj1*wj1+vj2*wj2+ +vjk*wjk。（其中*为乘号） 请你帮助金明设计一个满足要求的购物单。,5.开心的金明,【输入文件】 输入文件happy.in 的第1行，为两个正整数，用一个空格隔开： N m （其中N（30000）表示总钱数，m（25）为希望购买物品的个数。） 从第2行到第m+1行，第j行给出了编号为j-1的物品的基本数据，每行有2个非负整数 v p （其中v表示该物品的价格(

28、v=10000)，p表示该物品的重要度(15)） 【输出文件】 输出文件happy.out只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（100000000）。 【输入样例】 1000 5 800 2 400 5 300 5 400 3 200 2 【输出样例】 3900,6.金明的预算方案,金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间金明自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N元钱就行”。今天一早，金明就开始做预算了，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的，下表就

29、是一些主件与附件的例子：主件 附件电脑 打印机，扫描仪书柜 图书书桌 台灯，文具工作椅 无 如果要买归类为附件的物品，必须先买该附件所属的主件。每个主件可以有0个、1个或2个附件。附件不再有从属于自己的附件。金明想买的东西很多，肯定会超过妈妈限定的N元。于是，他把每件物品规定了一个重要度，分为5等：用整数15表示，第5等最重要。他还从因特网上查到了每件物品的价格（都是10元的整数倍）。他希望在不超过N元（可以等于N元）的前提下，使每件物品的价格与重要度的乘积的总和最大。 设第j件物品的价格为vj，重要度为wj，共选中了k件物品，编号依次为j1，j2，jk，则所求的总和为：vj1*wj1+vj2

30、*wj2+ +vjk*wjk。（其中*为乘号）请你帮助金明设计一个满足要求的购物单。,6.金明的预算方案,【输入文件】 输入文件的第1行，为两个正整数，用一个空格隔开： N m 其中N（0，表示该物品为附件，q是所属主件的编号）【输出文件】输出文件只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值 （200000）。,6.金明的预算方案,【输入样例】 1000 5 800 2 0 400 5 1 300 5 1 400 3 0 500 2 0 【输出样例】 2200,转化为01背包问题 考虑到每个主件最多只有两个附件，因此我们可以通过转化，把原问题转化为01背包问题来解决，在

31、用01背包之前我们需要对输入数据进行处理，把每一种物品归类，即：把每一个主件和它的附件看作一类物品。处理好之后，我们就可以使用01背包算法了。在取某件物品时，我们只需要从以下四种方案中取最大的那种方案：只取主件、取主件附件1、取主件附件2、既主件附件1附件2。很容易得到如下状态转移方程： fi,j=maxfi-1,j， fi-1,j-ai,0+ai,0*bi,0， fi-1,j-ai,0-ai,1+ai,0*bi,0+ai,1*bi,1， fi-1,j-ai,0-ai,2+ai,0*bi,0+ai,2*bi,2， fi-1,j-ai,0-ai,1-ai,2+ai,0*bi,0+ai,1*bi,

32、1+ai,2*bi,2 其中，fi,j表示用j元钱，买前i类物品，所得的最大值，ai,0表示第i类物品主件的价格，ai,1表示第i类物品第1个附件的价格，ai,2表示第i类物品第2个附件的价格，bi,0,bi,1,bi,2分别表示主件、第1个附件和第2个附件的重要度。fi-1,j表示把j元钱全部投入前i-1类物品所得的最大值，即不取第i类物品这一方案，fi-1,j-ai,0+ai,0*bi,0表示只取第i类物品的主件这一方案，fi-1,j-ai,0-ai,1+ai,0*bi,0+ai,1*bi,1，表示取第i类物品的主件和第个附件这一方案，fi-1,j-ai,0-ai,2+ai,0*bi,0+

33、ai,2*bi,2，表示取第i类物品的主件和第2个附件这一方案，fi-1,j-ai,0-ai,1-ai,2+ai,0*bi,0+ai,1*bi,1+ai,2*bi,2，则表示取第i类物品的主件和两个附件这一方案。,var a:array160,03 of integer;/a数组用来存放每一类物品，ai,3用来保存每类物品主件的编号 b:array160,02 of integer; f:array060,03200 of integer; n,m,i,s,v,p,q,j:integer; begin fillchar(a,sizeof(a),0); fillchar(b,sizeof(b),

34、0); readln(n,m); n:=n div 10; s:=0; for i:=1 to m do begin readln(v,p,q);/读入数据 v:=v div 10;/优化，因为每个物品的价格是10的整数倍 if q=0 then begin/主件 inc(s); as,0:=v; as,3:=i; bs,0:=p; end else begin/是附件 for j:=1 to s do/此循环用来查找该附件的主件，找到后就退出循环 if aj,3=q then break; if aj,1=0 then begin aj,1:=v;bj,1:=p; end else begi

35、n aj,2:=v;bj,2:=p; end; end; end;,fillchar(f,sizeof(f),0); m:=s;/处理完输入数据后，s为共有多少类物品 for i:=1 to m do/对m类物品进行动态规划，枚举物品 for j:=0 to n do/枚举状态 begin/找最优的方案 fi,j:=fi-1,j;/不取第i类物品 if (j=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,jfi-1,j-ai,0-ai,1-ai,2+ai,0*bi,0+a

36、i,1*bi,1+ai,2*bi,2) then fi,j:=fi-1,j-ai,0-ai,1-ai,2+ai,0*bi,0+ai,1*bi,1+ai,2*bi,2; end; writeln(fm,n*10); end.,7.最长公共子序列,最长公共子序列：字符序列的子序列是指从给定字符序列中随意地（不一定连续）去掉若干个字符（可能一个也不去掉）后所形成的字符序列。令给定的字符序列X=“x0，x1，.，xm -1“，序列Y=“y0，y1，.，yk-1“是X的子序列，存在X的一个严格递增下标序列，使得对所有的j=0，1，.，k-1，有xij= yj。例如，X=“ABCBDAB“，Y=“BCDB

37、“是X的一个子序列。给定两个序列A和B，称序列Z是A和B的公共子序列，是指Z同是A和B的子序列。问题要求已知两序列A和B的最长公共子序列。,我们以ACDEFACDE与CCACDEFCD两个序列为例，研究求最长公共子序列的做法。,不难发现，最长公共子序列与斜线的关系有关。我们要将上图的5连斜线与2连斜线接上！,d0,0:=0; for i:=1 to n do di,0:=0; for j:=1 to m do d0,j:=0; /初始化 for i:=1 to n do for j:=1 to m do if s1i=s2j then di,j:=di-1,j-1+1 else begin i

38、f di-1,jdi,j-1 then di,j:=di-1,j else di,j:=di,j-1; end;,下面我们给出一个基本的程序段,8.回文词,【题目描述】（vijos1327） 回文词是一种对称的字符串也就是说，一个回文词，从左到右读和从右到左读得到的结果是一样的。任意给定一个字符串，通过插入若干字符，都可以变成一个回文词。你的任务是写一个程序，求出将给定字符串变成回文词所需插入的最少字符数。 比如字符串“Ab3bd”，在插入两个字符后可以变成一个回文词（“dAb3bAd”或“Adb3bdA”）。然而，插入两个以下的字符无法使它变成一个回文词。,【输入格式】 第一行包含一个整数N

39、，表示给定字符串的长度，3=N=5000 第二行是一个长度为N的字符串，字符串由大小写字母和数字构成。 【输出格式】 一个整数，表示需要插入的最少字符数。 【样例输入】 5 Ab3bd 【样例输出】 2,谁能够用刚刚我们讲到的最长公共子序列来解决这道题呢？,这道题看起来与最长公共子序列毫无关系，但是如果我们将字符串倒过来就会发现其中的精妙之处。 在这里我们以样例 A b 3 b d为例 S（原串） A b 3 b d S1（倒序串） d b 3 b A LCS b 3 b 我们实际需要添加的使其成为回文词的只有不在lcs中的A和d而已。下面谁能想到怎么写递推式？,var a,b:array11

40、000of char; f:array01000,01000of longint; n,i,j:integer; function max(x,y:longint):longint; begin if xy then exit(x) else exit(y); end; Begin readln(n); for i:=1 to n do begin read(ai); bn-i+1:=ai; /制作S2 end; for i:=1 to n do /LCS for j:=1 to n do if ai=bj then fi,j:=fi-1,j-1+1 else fi,j:=max(fi-1,j

41、,fi,j-1); writeln(n-fn,n); /输出需要配对的字符数 end.,思考题： 如果是3个字符串求最长公共子序列又该怎么做呢？,9.区间dp,合并：意思就是将两个或多个部分进行整合，当然也可以反过来，也就是是将一个问题进行分解成两个或多个部分。 特征：能将问题分解成为两两合并的形式 求解：对整个问题设最优值，枚举合并点，将问题分解成为左右两个部分，最后将左右两个部分的最优值进行合并得到原问题的最优值。有点类似分治算法的解题思想。 典型试题：整数划分，凸多边形划分、石子合并、多边形合并、能量项链等。,10.整数划分,给出一个长度为n的数 要在其中加m-1个乘号，分成m段 这m段

42、的乘积之和最大 mn=20 有T组数据，T=10000,10.整数划分,给出一个长度为n的数 要在其中加m-1个乘号，分成m段 这m段的乘积之和最大 mn=20 有T组数据，T=10000,10.整数划分,可以先预处理出原数第i到j段的数值Ai,j是多少，这样转移就方便了，预处理也要尽量降低复杂度。 Fi，j表示把这个数前i位分成j段得到的最大乘积。 Fi,j=Fk,j-1*Ak+1,i, 1ki=n, j=m 时间复杂度为Omn2,请大家想一想这道题的循环应该怎么写？,11.石子合并,【题目描述】 在一个园形操场的四周摆放N堆石子,现要将石子有次序地合并成一堆.规定每次只能选相邻的2堆合并成

43、新的一堆，并将新的一堆的石子数，记为该次合并的得分。 试设计出1个算法,计算出将N堆石子合并成1堆的最小得分和最大得分. 【输入格式】 数据的第1行试正整数N,1N100,表示有N堆石子.第2行有N个数,分别表示每堆石子的个数. 【输出格式】 输出共2行,第1行为最小得分,第2行为最大得分. 【输入样例】 4 4 4 5 9 【输出样例】 43 54,11.石子合并,这道题是不是和整数划分有很多相似之处，这也是一道区间dp题。 但有一点非常不同，石子合并是在圆形操场，也就是说这不是一个线性的dp问题而是一个环形的dp问题，遇到这种题目我们又该如何去解决呢？,从这道题目来看，它是一个环形的结构，

44、因此我们可以把这个环从某个点分开，然后扩展成为两倍，从而更加方便的枚举各个区间，解决了回环往复的问题，这个处理方法还应用在usaco1.1 破碎的项链，还有能量项链的解题之中。,状态转移方程： fj,p:=maxfj,k+fk+1,p+sumj,p gj,p:=mingj,k+gk+1,p+sumj,p (其中的sum数组表示两点之间的和，包括两点)。,最后请问大家在变成两倍后我们解存在哪里？,我们只要找所有长度为n的区间内的最大值即可！,var f,g:array0200,0200 of longint; map:array0200 of longint; n:longint; proced

45、ure init; var i:longint; begin fillchar(f,sizeof(f),0); filldword(g,sizeof(g)2,maxint*500); readln(n); for i:=1 to n do begin read(mapi); mapi+n:=mapi; end; for i:=1 to 2*n do begin fi,i:=0; gi,i:=0; end; end;,function sum(a,b:longint):longint; var i:longint; begin sum:=0; for i:=a to b do inc(sum,m

46、api); exit(sum); end; function max(a,b:longint):longint; begin if ab then exit(a) else exit(b); end; function min(a,b:longint):longint; begin if ab then exit(a) else exit(b); end;,procedure dp; var i,j,k,ans,p,ans1:longint; begin ans:=0; ans1:=maxlongint; for i:=1 to n do for j:=1 to 2*n-i-1 do begin p:=i+j; for k:=j to p-1 do begin fj,p:=max(fj,p,fj,k+fk+1,p+sum(j,p); gj,p:=min(gj,p,gj,k+gk+1,p+sum(j,p); end; end; for i:=1 to n do begin if fi,i+n-1ans then ans:=fi,i+n-1; if gi,i+n-1ans1 then ans1:=gi,i+