动态规划总结ppt课件.ppt

《动态规划总结ppt课件.ppt》由会员分享，可在线阅读，更多相关《动态规划总结ppt课件.ppt（109页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、DP的复习与提高最长不下降子序列模型设有整数序列b1,b2,b3,bn, 若存在i1i2i3im, 且bi1bi2bi3bim, 则称b1,b2,b3,bn,中有长度为M的不下降序列bi1，bi2，bi3，bim。求序列b1,b2,b3,bn中所有长度（M）最大不下降序列。输入：整数序列输出：最大长度M和所有长度为M的序列个数T分析: 设h1.n表示n个输入的整数； 令fi表示从第i个数开始到第m个数的最长不下降子序列的长度，则有： fi = max(fj+1)(1=i=n-1, i+1=j=n, hi=hj) 边界为fn := 1 具体求解时用倒推，for i:=n-1 downto 1 时

2、间复杂性：O(n2)顺推的算法设f(i)为前i个数中的最大不下降序列长度 , 则 f(i)=maxf(j)+1 (1=ji=n, hjhi) 边界为F(1)=1 下面的优化算法是以顺推方向进行的.优化 如果当n=100000时，显然上述算法要超时。 从DP的基本优化思路着手，也就是去除一些一定不会有最优解产生的状态。例如：fi=3; hi=10; fj=3; hj=5,那么无论具体的搭配情况如何，状态j都要比状态i优秀。也就是说，我们只需要保留当前长度为i的序列中最后一个数字即可，并且这个数是所有长度为i的不下降序列中最后一个数的最小值。 由此，算法的本质也发生了变化。 设bi表示长度为i的不

3、下降序列的最后一个元素的最小值。 初始化：bi:=maxlongint, b1 := h1 容易看出，b数组一定是不下降序列。 当处理hi时，用二分法查找它可以连接到长度最大为多少的不下降子序列的之后（查找区间的左右边界是1i）。 假设可以连到长度最大为y的不上升子序列后，则by+1:=minby+1,hi。在找到hi的最终位置后,也就知道了前i个数的最长不下降序列的长度了,这时就可记录fi的值. 最后，b数组被赋值的元素最大下标就是问题的答案。 在实现时要仔细考虑一些细节情况.1.求最长不下降序列参考程序:const maxn=100000;var h,b,f:array1.maxn of

4、longint; n,i,j,k,l,r,m:longint; found :boolean;begin readln(n); for i:=1 to n do read(hi); for i:=1 to n do bi := maxlongint; b1 := h1; f1 := 1; for i:=2 to n do begin l:=1; r:= i; while l r do begin m := (l+r) div 2; if bm hi then begin bl := hi; fi := l; end else fi := l+1; end; j:=0; for i:=1 to

5、n do if bi maxlongint then inc(j) else break; writeln(j); for i:=1 to j do write(bi:4); writeln; for i:=1 to n do write(fi:4);end.数据f存储了以每个元素结尾的最长不下降序列的长度.注意：两个程序的主要区别在于二分查找时对于bm=hi时的处理方法不同。对于严格递增序列来说，出现相等时，不增加序列长度。对于不降序列来说，则要增加序列长度。 2. 求严格递增序列const maxn=100000;var h,b,f:array1.maxn of longint; n,i,

6、j,k,l,r,m:longint; found :boolean;begin readln(n); for i:=1 to n do read(hi); for i:=1 to n do bi := maxlongint; b1 := h1; f1 := 1; for i:=2 to n do begin l:=1; r:= i; found := false; while l hi then r := m-1 else if bm hi then begin bl := hi; fi := l; end else begin bl+1 := hi; fi := l+1; end end;

7、j:=0; for i:=1 to n do if bi maxlongint then inc(j) else break; writeln(j); for i:=1 to j do write(bi:4); writeln; for i:=1 to n do write(fi:4);end.最长不下降序列拓展1、求序列中最长不下降序列的个数。 设ti为以i结尾的最长不下降序列的个数,则 Ti=tj (1=ji=n , hj=hi, fi=fj+1) 边界为:t1=1 当fi=n时，将ti累加 举例： h: 1 2 3 4 6 5 8 10 9 f: 1 2 3 4 5 5 6 7 7 t:

8、 1 1 1 1 1 1 2 2 2答案：f=7时，个数为t=4最长不下降序列拓展2、求本质不同的最长不下降序列的个数。(注:其实这里讨论的是单调递增序列)求本质不同的最长不下降序列个数有多少个？如：1 2 3 4 6 5 8 10 9 有， 1 2 3 4 6 8 10 , 1 2 3 4 5 8 10, 1 2 3 4 6 8 9 ,1 2 3 4 5 8 9 都是本质不同的。但对于 h 1 2 2 3 3 5 4 5 f 1 2 2 3 3 4 4 4 t 1 1 1 2 2 4 4 4 答案有8个，其中4个1 2 3 5 ，4个1 2 3 4正确答案应该是两个.上例显然对于原序列h中两

9、个相同的数，重复算了多次因此，我们对算法进行改进：对原序列按h从小到大（当hi=hj时按F从大到小）排序，增设Orderi记录新序列中的i个数在原序列中的位置。可见，求ti时，当fj=fj+1,hj=hj+1且Orderj+1Orderi时，便不累加tj。这样就避免了重复。 上述算法的时间复杂度为O(n2) 这个算法也存在问题.对于 h 1 2 2 3 3 5 4 5 f 1 2 2 3 3 4 4 4 t 1 1 1 2 2 4 4 4将得出3的错误答案如果改为统计最后结果时要求(fi = fj = maxlen) 且 (hi hj),则下面的数据又会出现错误答案: h 1 3 4 5 1

10、2 3 5 f 1 2 3 4 1 2 3 4 程序输出为1正确应该是2错误程序1: 按PPT中的算法执行const maxn=10000;var h,f,t,order:array1.maxn of longint; n,i,j,k,max, mlen:longint;procedure swap(var a,b:longint);var x:longint;begin x:= a; a:=b; b:=x;end;begin readln(n); for i:=1 to n do read(hi); mlen:=0; for i:=1 to n do begin read(fi); if f

11、i mlen then mlen := fi; end; for i:=1 to n+1 do orderi := i; hn+1 := maxlongint; fn+1 := mlen+1; inc(n); for i:=1 to n-1 do for j:=n downto i+1 do if hj-1 hj then begin swap(hj-1,hj); swap(fj-1,fj); swap(orderj-1,orderj); end else if hj-1 = hj then begin if fj-1 fj then begin swap(hj-1,hj); swap(fj-

12、1,fj); swap(orderj-1,orderj); end; end; t1 := 1; for i:=2 to n do for j:= i-1 downto 1 do if (hj hi) and (fj+1 = fi) then if not ( hj=hj+1) and (fj=fj+1) and(orderj+1 mlen then mlen := fi; end; for i:=1 to n+1 do orderi := i; hn+1 := maxlongint; fn+1 := mlen+1; inc(n); for i:=1 to n do if fi = 1 the

13、n ti := 1; for k:=2 to mlen+1 do for i:=n downto 1 do if fi = k then begin j:=i-1; while (j0) and (hj hi ) do begin if (hj mlen then mlen := fi; end; for i:=1 to n+1 do orderi := i; hn+1 := maxlongint; /建立哨兵 fn+1 := mlen+1; inc(n); t1:=1; /前一个程序中仅有的改动 for k:=2 to mlen+1 do for i:=n downto 1 do if fi

14、 = k then begin j:=i-1; while (j0) and (hj hi ) do begin if (hj hi) and (fj+1=k) then inc(ti, tj); dec(j); end; end; writeln(tn);end.测试数据71 2 2 3 3 5 41 2 2 3 4 4 491 2 3 4 6 5 8 10 91 2 3 4 5 5 6 7 781 2 2 3 3 5 4 51 2 2 3 4 4 4 58 1 2 1 2 3 3 5 41 2 1 2 3 3 4 4 81 3 4 5 1 2 3 51 2 3 4 1 2 3 4但这组数据

15、过不了:82 3 4 5 1 2 3 51 2 3 4 1 2 3 4经典赛题1、导弹拦截（注意：第二问不可以用每次删除最长不上升序列的方法做。比如，当来袭的导弹共有4颗，高度依次为2 4 1 3的时候，如果不巧找到的最长不上升序列为4 1，那么剩下的2和3就只能另外启用两套系统了。这显然不是最优解。 ） 第二问用贪心法即可。每颗导弹来袭时，使用能拦截这颗导弹的防御系统中上一次拦截导弹高度最低的那一套来拦截。若不存在符合这一条件的系统，则使用一套新系统。 合唱队形合唱队形【问题描述【问题描述】N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。合唱队形是指

16、这样的一种队形：设K位同学从左到右依次编号为1, 2, , K，他们的身高分别为T1, T2, , TK，则他们的身高满足T1 T2 Ti+1 TK (1iK)。你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。输入文件输入文件chorus.in的第一行是一个整数N(2=N=100)，表示同学的总数。第一行有n个整数，用空格分隔，第i个整数Ti(130=Ti=230)是第i位同学的身高(厘米)。-输出文件输出文件chorus.out包括一行，这一行只包含一个整数，就是最少需要几位同学出列。-样例输入8186186150200160130197220-

17、样例输出4 设有N*N的方格图(N=10,我们将其中的某些方格中填入正整数,而其他的方格中则放入数字0。如下图所示（见样例）：方格取数？（可以用最长不下降模型吗？）方格取数？（可以用最长不下降模型吗？）对比对比VIJOS 飞翔飞翔飞翔飞翔 http:/:8080/JudgeOnline/showproblem?problem_id=1907某人从图的左上角的A 点出发，可以向下行走，也可以向右走，直到到达右下角的B点。在走过的路上，他可以取走方格中的数（取走后的方格中将变为数字0）。此人从A点到B 点共走两次，试找出2条这样的路径，使得取得的数之和为最大。 输输 入入 输入的第一行为一个整数N

18、（表示N*N的方格图），接下来的每行有三个整数，前两个表示位置，第三个数为该位置上所放的数。一行单独的0表示输入结束。 输输 出出 只需输出一个整数，表示2条路径上取得的最大的和。后面是另外思路的DP参考解答分析: 这是一道所谓”路径”类型的DP题.这道题的阶段划分方法有两种:较为简单的一种是按行划分阶段,按列划分状态. 如果人只从A点到B点走一次,则可以用DP较方便的解决:从A开始,向下向下递推,依次求出从A点出发到达当前位置(i,j)所能取得的最大的数之和,存放在sum数组中.原始数据存放在data数组中.为处理方便, sum数组加进了0行和0列. 状态转移方程为: Sumi,j = ma

19、xsumi-1,j, sumi,j-1 + datai,j (1=i=n, 1=j=n)如果走两次,能不能够用DP先走一次,求得最大数和, 把路径上的数清0,然后再用DP走一次,求得第二最大数和,再把两次的结果相加得到最后的结果呢?这是一种很自然的想法,并且对测试样例也是正确的.但实际这种算法是错误的.例如,对右图数据,若按DP先走一次,将取完红色字体的数,但第二次DP时,两个黑色的数字将无法同时取到.而事实我们可以简单地将第3列和第5列的所有数取完.因此本题所谓走两次其实必须在一次DP时同时考察两条路径.3233443考虑两个人同时从A出发,则需要考虑两个人到达任意两个格子(i1,j1)(i

20、2,j2)的情况.即状态要用4个变量来描述:sumi1,j1,i2,j2每个人可以从上或左的两个方向达到当前格子,显然前一状态必为:(i1-1,j1), (i2-1,j2)(i1-1,j1),(i2, j2-1)(i1,j1-1),(i2-1,j2)(i1,j1-1),(i2,j2-1)四种情况之一.设p=maxsumi1-1,j1, i2-1,j2, sumi1-1,j1,i2, j2-1, sumi1,j1-1,i2-1,j2,sumi1,j1-1,i2,j2-1则有j2)j1or i2(i1 j2datai2, j1datai1, pj2)j1 and i2(i1 j1datai1,p2

21、j2,i1,j1,sumi据此,可写出程序.易知,本算法的时间空间复杂度均为O(n4)后一段分析是按对角线方向来划分阶段的.这样处理之后, 可以把时间复杂性降低一维,把空间复杂性降低到O(n2), 因此该思想方法要认真思考, 掌握优化方法优化方法: 1、状态的设计、状态的设计 对于本题来说，状态的选定和存储对整个问题的处理起了决定性的作用。我们从（1，1）出发，每走一步作为一个阶段，则可以分成2*n-1个阶段： 第一个阶段，两条路径从（1，1）出发； 第二个阶段，两条路径可达（2，1）和（1，2）； 第三个阶段，两条路径可达的位置集合为（3，1）、（2，2）和（1，3）； 第2*n-1个阶段，

22、两条路径汇聚（n，n）；在第k(1k2*n-1)个阶段，两条路径的终端坐标（x1，y1）（x2，y2）位于对应的右下对角线上。如下图所示：阶段1阶段2 阶段3 阶段4阶段5阶段6阶段7如果我们将两条路径走第i步的所有可能位置定义为当前阶段的状态的话，面对的问题就是如何存储状态了。方格取数问题的状态数目十分庞大，每一个位置是两维的，且又是求两条最佳路径，这就要求在存储上必须做一定的优化后才有可能实现算法的程序化。主要的优化就是：舍弃一切不必要的存储量。为此，我们取位置中的x坐标（x1，x2）作状态，其中（1x1n）and（1x2n）直接由x坐标计算对应的y坐标：（y1=k+1-x1）and（y1

23、1n）and（y2=k+1-x2）and（y21n 阶段1阶段2 阶段3 阶段4阶段5阶段6阶段72、状态转移方程、状态转移方程设两条路径在k阶段的状态为（x1，x2）。由（y1=k+1-x1）（y1 1.n）得出第一条路径的坐标为（x1，y1）；由（y2=k+1-x2）（y2 1.n）得出第二条路径的坐标为（x2，y2）。假设在k-1阶段，两条路径的状态为（x1，x2）且（x1，x2）位于（x1，x2）状态的左邻或上邻位置。因此我们设两条路径的延伸方向为d1和d2：di=0，表明第i条路径由（xi，yi）向右延伸至（xi，yi）；di=1，表明第i条路径由（xi，yi）向下延伸至（xi，yi

24、）（1i2）。显然（x1= x2）（d1= d2），表明两条路径重合，同时取走了（x1，y1）和（x1，y1）中的数，这种取法当然不可能得到最大数和的。分析两种可能：若x1=x2，则两条路径会合于x1状态，可取走（x1，y1）中的数(如下图)； x2(x1) x1(x2) x1=x2 若x1x2，则在k阶段，第一条路径由x1状态延伸至x1状态，第二条路径由x2状态延伸至x2状态，两条路径可分别取走（x1，y1）和（x2，y2）中的数(如下图)；X1X1X2X2设 fk，x1，x2在第k阶段，两条路径分别行至x1状态和x2状态的最大数和。显然k=1时，时，f1，1，1=data1,1；k2时，时

25、，fk，x1，x2=maxfk-1， x1，x2+datax1，y1(x1=x2)，fk-1， x1，x2+datax1，y1+datax2，y2(x1x2) 1k2*n-1，x1可达可达x1的状态集合，的状态集合，x2可达可达x2的状态集合，（的状态集合，（x1x2）(d1d2)；上述状态转移方程符合最优子结构和重叠子问题的特性，因此适用于动态程序设计方法求解。由于第由于第k个阶段的状态转移方程仅与第个阶段的状态转移方程仅与第k-1个阶段的状态发生联系个阶段的状态发生联系，因此不妨设 f0第k-1个阶段的状态转移方程； f1第k个阶段的状态转移方程；初始时，f01，1=0。经过2*n-1个阶

26、段后得出的f0n，n即为问题的解。此为空间优化！此为空间优化！3、多进程决策的动态程序设计多进程决策的动态程序设计 由于方格取数问题是对两条路径进行最优化决策的，因此称这类动态程序设计为分阶段、多进程的最优化决策过程。设阶段i：准备走第i步（1i2*n-1）；状态（x1，x2）： 第i步的状态号（1x1，x2i。x1，x21.n）决策（d1，d2）：第一条路径由x1状态出发沿d1方向延伸、第二条路径由x2状态 出发沿d2方向延伸，可使得两条路径的数和最大（0d1，d21。方向0表示右移，方向1表示下移）；本题的启示:1.如果某个状态变量可以由另一个状态变量计算产生(例如y坐标可由x坐标计算生成

27、),则这个状态变量可以不保存;这样可以压缩状态.2.如果K阶段的状态只与K-1阶段的状态值有关,则可以利用滚动数组,只保留前后两个阶段的状态值.初值状态值保存在F0中,然后由F0去递推计算F1,每次计算完成后,又将F1的值赋值到F0中,以便下一阶段的计算.fillchar(f0，sizeof(f0)，0)；行走前的状态转移方程初始化f01，1data1,1；for i2 to 2*n-1 do阶段：准备走第i步 begin fillchar(f1，sizeof(f1)，0)； 走第i步的状态转移方程初始化 for x11 to i do枚举两条路径在第i-1步时的状态x1和x2 for x21

28、 to i do begin 计算y1和y2； if (x1，y1)和(x2，y2)在界内 then for d10 to 1 do 决策：计算两条路径的最佳延伸方向 for d20 to 1 do begin 第1条路径沿d1方向延伸至(x1，y1）； 第2条路径沿d2方向延伸至(x2，y2)； if (x1，y1)和(x2，y2)在界内 计算第i步的状态转移方程then f1x1，x2maxf0 x1，x2+datax1，y1 x1=x2，f0 x1，x2+datax1，y1+datax2，y2 x1x2 end；for end；for f0f1；记下第i步的状态转移方程end；for输出

29、两条路径取得的最大数和f0n，nconst maxn=20; dir:array1.2,1.2 of integer= (-1,0), (0,-1);var a, f0,f1:array0.maxn,0.maxn of integer; n, i,j,k,d1,d2:integer; x1,y1, x2, y2,x1p,y1p, x2p, y2p,max:integer;begin readln(n); readln(i,j,k); while not (i=0) and (j=0) and (k=0) do begin ai,j := k; readln(i,j,k); end; f01,1

30、 := a1,1; for k:=2 to 2*n -1 do begin fillchar(f1, sizeof(f1), 0); for x1:=1 to k do begin y1:=k+1-x1; if (x1=n) and (1=y1) and (y1=n) then begin for x2:=1 to k do begin y2:=k+1-x2; if (x2=n) and (1=y2) and (y2 max then max := f0 x1p,x2p; end; if (x1=x2) and (y1=y2) then f1x1,x2 := max + ax1,y1 else

31、 f1x1,x2 := max + ax1,y1 + ax2,y2; end; end; end; end; f0:=f1; end; writeln(f0n,n);end.类似题目: Vijos P1143 三取方格数数塔模型如下所示一个数字三角形 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5写一个程序计算从顶至底的某处的一条路径，使该路径所经过的数字和最大每一步可沿直向下或 右斜线向下走1三角形行数=100三角形中的数字为整数0，1，99分析: 设：fi,j为从第i行中的第j个数至第n行的最大的数字和；则: fn,j=an,j ( 1=j=n ) fi,j=maxfi+1,j

32、 , fi+ 1,j+1 + ai,j (1=j=i, 1=i=n-1) f1,1即为所求。经典例题: 花店橱窗布置参见教材P230 例8-5On the Web:http:/ 【题目描述【题目描述】 假设你想以最美观的方式布置花店的橱窗。现在你有F束不同品种的花束，同时你也有至少同样数量的花瓶被按顺序摆成一行。这些花瓶的位置固定于架子上，并从1至V顺序编号，V是花瓶的数目，从左至右排列，则最左边的是花瓶1，最右边的是花瓶V。花束可以移动，并且每束花用1至F间的整数唯一标识。标识花束的整数决定了花束在花瓶中的顺序，如果IJ，则令花束I必须放在花束J左边的花瓶中。 例如，假设一束杜鹃花的标识数为

33、1，一束秋海棠的标识数为2，一束康乃馨的标识数为3，所有的花束在放入花瓶时必须保持其标识数的顺序，即：杜鹃花必须放在秋海棠左边的花瓶中，秋海棠必须放在康乃馨左边的花瓶中。如果花瓶的数目大于花束的数目。则多余的花瓶必须空置，且每个花瓶中只能放一束花。 每一个花瓶都具有各自的特点。因此，当各个花瓶中放入不同的花束时，会产生不同的美学效果，并以美学值（一个整数）来表示，空置花瓶的美学值为零。在上述例子中，花瓶与花束的不同搭配所具有的美学值，如下表所示。 花 瓶 1 2 3 4 5 1 (杜鹃花) 7 23 -5 -24 16 2 (秋海棠) 5 21 -4 10 23 3 (康乃馨) -21 5 -

34、4 -20 20例如，根据上表，杜鹃花放在花瓶2中，会显得非常好看；但若放在花瓶4中则显得十分难看。 为取得最佳美学效果，你必须在保持花束顺序的前提下，使花束的摆放取得最大的美学值。如果有不止一种的摆放方式具有最大的美学值，则其中任何一直摆放方式都可以接受，但你只要输出任意一种摆放方式。（2）假设条件 1F100，其中F为花束的数量，花束编号从1至F。 FV100，其中V是花瓶的数量。 -50Aij50，其中Aij是花束i在花瓶j中的美学值。（3）输入 第一行包含两个数：F，V。 随后的F行中，每行包含V个整数，Aij 即为输入文件中第（i+1 ）行中的第j个数。（4）输出一行，表示程序所产生

35、摆放方式的美学值。样例输入：3 5 7 23 -5 -24 165 21 -4 10 23-21 5 -4 -20 20样例输出：53 分析: 将问题进行转化，找出问题的原型。将摆放方案的要求用表格表现出来，则摆放方案需要满足：（1）每行选且只选一个数（花瓶），（2）摆放方案的相邻两行中，下面一行的花瓶编号要大于上面一行的花瓶编号。这样可将问题转化成：给定一个数字表格，求解从顶行至底行的一条路径，使得这条路径所经过的数字总和最大，要求满足两个条件：（1）每行选且仅选一个数字；（2）路径中相邻两行数字，必须保证下一行数字的列数大于上一行数字的列数。对比数塔原型，写出动态规划转移方程。设bi,j表

36、示美学值表格中第i行的第j个数字，用qi,j表示从表格最底层到bi,j这个数字的最佳路径的数字和，F表示花束总数，V表示花瓶总数，则有：边界： qi, V+1 := - (1=i=F) qF,j := bF,j (1=j=V) 状态转移方程：qi,j := maxqi+1, k (j+1=k=V+1) + bi,j (1=i=F-1, 1=j=V)这样，得出的maxq1,j (1=j=V)就是最大的美学值。算法复杂性为：O（FV2）优化看一下这样两个状态的求解方法：qi,j = maxqi+1,k (j+1=k=V+1) + bi,jqi,j+1 = maxqi+1,k (j+2=k=V+1)

37、+bi,j+1上面两个状态中求maxqi+1,k的过程中进行了大量重复的比较，非常费时。对状态的表示作修改，用数组ti,j表示第i行从第j列起到V列的美学值的最大值，即：ti,j = maxqi,k (j=k=V) (1=i=F, 1=j=V)表示新的状态。经过修改后，因为qi,j = ti+1,j+1 + bi,j, 而ti,j = maxti,j+1, qi,j (1=i=F, 1=j=V)所以得出新的状态转移方程：tF,j = max tF,j+1, bF,j (1=j=V)ti,j = maxti, j+1, ti+1,j+1+bi,j (1=j=V, 1=i=F-1)这样，得出的最大

38、美学值为t1,1，新算法的时间复杂度为O(FV)最小代价子母树模型 有n堆石子排成一条直线，每堆石子有一定的重量。现在要合并这些石子成为一堆石子，但是每次只能合并相邻的两堆。每次合并需要消耗一定的体力，该体力为所合并的两堆石子的重量之和。问最少需要多少体力才能将n堆石子合并成一堆石子？ 数据规模:n=3000 样例输入: 8 5 2 4 7 6 1 3 9 样例输出: 105分析令mi,j表示归并第i个数到第j数的最小代价,wi,j表示第i个数到第j个数的和，这个可以事先计算出来。wi,j可以在O(1)的时间内算出.有如下的状态转移方程: ji j)k(i ji,j1,kkminmi,ji 0

39、jmi,wm阶段：以归并石子的长度为阶段，一共有n-1个阶段。状态：每个阶段有多少堆石子要归并，当归并长度为2时，有n-1个状态；当归并长度为3时，有n-2个状态；当归并长度为n时，有1个状态。决策：当归并长度为2时，有1个决策；当归并长度为3时，有2个决策；当归并长度为n时，有n-1个决策。 for len := 2 to n do for i := 1 to n - len + 1 do begin j := i + len - 1; fi,j := MAXINT; for k:= i+1 to j do begin 参考上面状态转移方程求解优化不难发现这个算法的复杂度是n3。n的范围是3

40、000，需要优化算法。对于动态规划的优化和搜索的优化是一样的道理。搜索中，如果某状态下不会有最优解，那么就不用继续搜索下去了。动态规划也可以这样来优化。具体方法是：在计算每个状态的值的时候，记录下它所选取的分界点k，用si,j表示当mi,j取最优值的时候，选取的k值。那么原状态转移方程中的k的枚举范围便可以从原来的(i+1j)变为(si,j-1si+1,j)wi,j的优化方法:令ti表示 a1到ai的和, ti可以在输入数据时用O(n)的时间算出然后wi,j = tj-ti-1四边形不等式与决策单调性四边形不等式与决策单调性(证明略证明略)凸性：当函数wi,j满足：wi,j + wi，j =

41、wi,j + wi,j (i=ij=j) 时，称w满足四边形不等式。单调性：当函数wi,j满足：wi,j = wi,j (i=ij=j) 时,称w满足关于区间包含的单调性。这样，对于状态转移方程式：mi,j=minmi,k-1+mk,j+wi,j (ik=j)如果wi,j满足四边形不等式和区间包含单调性，那么mi,j也满足四边形不等式。用si,j表示mi,j的决策，如果函数mi,j满足四边形不等式，则函数si,j满足单调性，即决策单调性： si,j=si,j+=si+1,j+1。则函数si,j的值应该在一个区间内，即： si,j-1 = si,j = si+1,j由于si,j-1和si+1,j

42、已经在阶段j-i求出，所以在枚举决策变量k时，就可以从si,j-1到si+1,j。于是，我们利用si,j的单调性，得到优化的状态转移方程为： mi,j=0 i=j ij利用这样的决策单调性，就可以把时间复杂性优化到O(n2)。边界：si,i = i si,j的值在mi,j取得最优值时，保存、更新例如，对石子归并这道题，先验证wi,j满足区间单调性和四边形不等式。对数据 i i j j 2 3 7 4 6 5单调性： wi,j = 3+7+4=14 wi,j =2+3+7+4+6+5=27故 wi,j = wi,j 满足单调性, 1,min, 11,jiwjkmkimjimjiskjis四边形不

43、等式：wi,j + wi,j = (2+3+7+4) + (3+7+6+5) = 16+21 = 37wi,j + wi,j = (3+7+4) + (2+3+7+4+6+5) = 14 + 27 = 41故 wi,j + wi,j = wi,j + wi,j 故石子合并可利用四边形不等式进行优化。上述方法是具有普遍性的。对于状态转移方程与式类似，且wi,j满足四边形不等式的动态规划问题，都可以采用相同的优化方法，如最优二叉排序树（NOI96）等。用四边形不等式优化的经典题目石子合并-在一圆形操场四周摆放N堆石子(N2000),现要将石子有次序地合并成一堆.规定每次只能选相临的两堆合并成一堆,

44、并将新的一堆的石子数,记为该次合并的得分。编一程序,由文件读入堆数N及每堆石子数(20),(1)选择一种合并石子的方案,使得做N-1次合并,得分的总和最少 (2) 选择一种合并石子的方案,使得做N-1次合并,得分的总和最大输入数据: 第一行为石子堆数N; 第二行为每堆石子数,每两个数之间用一空格分隔.输出数据 :从第1至第N行为得分最小的合并方案. 第N+1行为空行.从N+2到2N+1行是得分最大的合并方案. 分析：用datai,j表示将从第i颗石子开始的接下来j颗石子合并所得的分值，mxi,j表示将从第i颗石子开始的接下来j颗石子合并可能的最大值，那么：mxi,j = max(mxi, k

45、+ mxi + k, j k + datai,k + datai+k, jk) (2=k=j)mxi,1 = 0同样的，我们用mni,j表示将第从第i颗石子开始的接下来j颗石子合并所得的最小值，可以得到类似的方程：mni,j = min(mni, k + mni + k, j k + datai,k + datai+k, j k) (0=k=j)mni,0 = 0这样，我们完美地解决了这道题。时间复杂度也是O(n2)。2：邮局(IOI2000) 问题描述按照递增顺序给出一条直线上坐标互不相同的n个村庄，要求从中选择p个村庄建立邮局，每个村庄使用离它最近的那个邮局，使得所有村庄到各自所使用的邮局

46、的距离总和最小。试编程计算最小距离和，以及邮局建立方案。 样例输入：10 512 3 6 7 9 11 22 44 50样例输出：92 7 22 44 50参见教材P234分析：将n个村庄按坐标递增依次编号为1，2，n，各个邮局的坐标为d1.n，状态表示描述为：mi,j表示在前j个村庄建立i个邮局的最小距离和。所以，mp,n即为问题的解，且状态转移方程和边界条件为：m1,j=w1,j ij其中wi,j表示在di.j之间建立一个邮局的最小距离和，可以证明，当仅建立一个邮局时，最优解出现在中位数，即设建立邮局的村庄为k，则， 于是，我们有：, 1, 1min,11jkwkimjimjki2/ )(

47、2/ )(jikjik或jilkdldjiw| |,2/ )(2/ )(jikjik或 ， 同时，令si,j=k，记录使用前i-1个邮局的村庄数，便于在算出最小距离和之后构造最优建立方案。上述算法中wi,j可通过O(n)时间的预处理（怎么预处理？），在O(1)的时间内算出，所以，该算法的状态总数为O(n*p)，每个状态转移的状态数为O(n)，每次状态转移的时间为O(1)，该算法总的时间复杂度为O(p*n2)。算法优化 - 本优化算法来自毛子青本题的状态转移方程与石子归并的状态转移方程十分相似，因此我们猜想其决策是否也满足单调性，即：si-1,jsi,jsi,j+1首先，我们来验证函数w满足四边

48、形不等式，即： 用样例输入数据可以进行验证。验证完成后，还应该证明mi,j满足四边形不等式和si,j满足单调性。这几步完成后，就可以利用决策单调性进行优化了。 , , ,jiwjiwjiwjiw,jjii 优化后的状态转移方程为：m1,j=w1,j , 1, 1min,1, 1jkwkimjimjiskjis si,j=k同上文所述，优化后的算法时间复杂度为O(n*p)。请在完成邮局的基础上，认真研究习题教材P74 8.4 书的复制四边形不等式优化的实质是对结果的充分利用。它通过分析状态值之间的特殊关系，推出了最优决策的单调性，从而在计算当前状态时，利用已经计算过的状态所做出的最优决策，减少了

49、当前的决策量。这就启发我们，在应用动态规划解题时，不仅可以实现状态值的充分利用，也可以实现最优决策的充分利用。这实际上是从另一个角度实现了“减少冗余”。3、能量项链 vijos 1312 在Mars星球上，每个Mars人都随身佩带着一串能量项链。在项链上有N颗能量珠。能量珠是一颗有头标记与尾标记的珠子，这些标记对应着某个正整数。并且，对于相邻的两颗珠子，前一颗珠子的尾标记一定等于后一颗珠子的头标记。因为只有这样，通过吸盘（吸盘是Mars人吸收能量的一种器官）的作用，这两颗珠子才能聚合成一颗珠子，同时释放出可以被吸盘吸收的能量。如果前一颗能量珠的头标记为m，尾标记为r，后一颗能量珠的头标记为r，

50、尾标记为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）=