DP-区间类型动态规划

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,区间类动态规划,长沙市雅礼中学 朱全民,整数划分,给出一个长度为,n,的数,要在其中加,m-1,个乘号，分成,m,段,这,m,段的乘积之和最大,mn=20,有,T,组数据，,T=10000,贪心法,尽可能平均分配各段，这样最终的数值将会尽可能大。但有反例。如,191919,分成,3,段,19,*,19,*,19=6859,但,191,*,91,*,9=156429,，显然乘积更大。,将一个数分成若干段乘积后比该数小，因为输入数不超过,20,位，因此不需高精度运算。,证明：,假设,AB,分成,A,和,B,且,A,BA*B(,相当于,B,个,A,相加,),同理可证明,A,B,为任意位也成立,动态规划,可以先预处理出原数第,i,到,j,段的数值,Ai,j,是多少，这样转移就方便了，预处理也要尽量降低复杂度。,Fi,，,j,表示把这个数前,i,位分成,j,段得到的最大乘积。,Fi,j,=Fk,j-1*Ak+1,i,1ki=n, j=m,时间复杂度为,Om,2,n,由于有,10000,组数据，因此估计时间复杂度为,10000,*,20,3,=8*10,7,至于说输出，记录转移的父亲就可以了。,石子合并,在一园形操场四周摆放,N,堆石子,(N100),；,现要将石子有次序地合并成一堆；,规定每次只能选相临的两堆合并成一堆,并将新的一堆的石子数,记为该次合并的得分。,选择一种合并石子的方案,使得做,N-1,次合并,得分的总和最少,选择一种合并石子的方案,使得做,N-1,次合并,得分的总和最大,示例,贪心法,N=5,石子数分别为,3 4 6 5 4 2,。,用贪心法的合并过程如下：,第一次,3 4 6 5 4 2,得分,5,第二次,5 4 6 5 4,得分,9,第三次,9 6 5 4,得分,9,第四次,9 6 9,得分,15,第五次,15 9,得分,24,第六次,24,总分：,62,然而有更好的方案：,第一次,3 4 6 5 4 2,得分,7,第二次,7 6 5 4 2,得分,13,第三次,13 5 4 2,得分,6,第四次,13 5 6,得分,11,第五次,13 11,得分,24,第六次,24,总分：,61,显然，贪心法是错误的。,分析,假设只有,2,堆石子，显然只有,1,种合并方案,如果有,3,堆石子，则有,2,种合并方案，,(1,2),3),和,(1,(2,3),如果有,k,堆石子呢？,不管怎么合并，总之最后总会归结为,2,堆，如果我们把最后两堆分开，左边和右边无论怎么合并，都必须满足最优合并方案，整个问题才能得到最优解。如下图：,动态规划,设,ti,j,表示从第,i,堆到第,j,堆石子数总和。,Fmax(i,j,),表示将从第,i,堆石子合并到第,j,堆石子的最大的得分,Fmin(i,j,),表示将从第,i,堆石子合并到第,j,堆石子的最小的得分,同理，,Fmaxi,i, = 0,，,Fmini,i, = 0,时间复杂度为,O(n,3,),优化,由于石子堆是一个圈，因此我们可以枚举分开的位置，首先将这个圈转化为链，因此总的时间复杂度为,O(n,4,),。,这样显然很高，其实我们可以将这条链延长,2,倍，扩展成,2n-1,堆，其中第,1,堆与,n+1,堆完全相同，第,i,堆与,n+i,堆完全相同，这样我们只要对这,2n,堆动态规划后，枚举,f(1,n),f(2,n+1),f(n,2n-1),取最优值即可即可。,时间复杂度为,O(8n,3,),如下图：,能量项链,在,Mars,星球上，每个,Mars,人都随身佩带着一串能量项链。,在项链上有,N,颗能量珠。,能量珠是一颗有头标记与尾标记的珠子，这些标记对应着某个正整数。,对于相邻的两颗珠子，前一颗珠子的尾标记一定等于后一颗珠子的头标记。如果前一颗能量珠的头标记为,m,，尾标记为,r,，后一颗能量珠的头标记为,r,，尾标记为,n,，则聚合后释放的能量为,mrn,（,Mars,单位），新产生的珠子的头标记为,m,，尾标记为,n,。,显然，对于一串项链不同的聚合顺序得到的总能量是不同的，请你设计一个聚合顺序，使一串项链释放出的总能量最大。,分析样例：,N=4,，,4,颗珠子的头标记与尾标记依次为,(2,，,3) (3,，,5) (5,，,10) (10,，,2),。,我们用记号表示两颗珠子的聚合操作，释放总能量：,(41)2)3,）,=10*2*3+10*3*5+10*5*10=710,动态规划,该题与石子合并完全类似。,设链中的第,i,颗珠子头尾标记为,(S,i-1,与,S,i,),。,令,F(i,j,),表示从第,i,颗珠子一直合并到第,j,颗珠子所能产生的最大能量，则有：,F(i,j,)=MaxF(i,k)+F(k+1,j)+S,i-1,*,S,k,*,S,j, i=kj,边界条件：,F(i,i,)=0,1=ikj=n,至于圈的处理，与石子合并方法完全相同，时间复杂度,O(8n,3,),。,凸多边形的三角剖分,给定由,N,顶点组成的凸多边形,每个顶点具有权值,将凸,N,边形剖分成,N-2,个三角形,求,N-2,个三角形顶点权值乘积之和最小？,样例,上述凸五边形分成,123,， ,135,， ,345,三角形顶点权值乘积之和为：,121,*,122,*,123+121,*,123,*,231+123,*,245,*,231= 12214884,分析,性质：一个凸多边形剖分一个三角形后，可以将凸多边形剖分成三个部分：,一个三角形,二个凸多边形（图,2,可以看成另一个凸多边形为,0,）,动态规划,如果我们按顺时针将顶点编号，则可以相邻两个顶点描述一个凸多边形。,设,f(i,j,),表示,ij,这一段连续顶点的多边形划分后最小乘积,枚举点,k,，,i,、,j,和,k,相连成基本三角形，并把原多边形划分成两个子多边形，则有,f(i,j,)=,minf(i,k)+f(k,j)+ai,*,aj,*,ak,1=ikj=n,时间复杂度,O(n,3,),讨论,为什么可以不考虑这种情况？,可以看出图,1,和图,2,是等价的，也就是说如果存在图,1,的剖分方案，则可以转化成图,2,的剖分方案，因此可以不考虑图,1,的这种情形。,多边形（,IOI98,）,多角形是一个单人玩的游戏，开始时有一个,N,个顶点的多边形。如图，这里,N=4,。每个顶点有一个整数标记，每条边上有一个,“,+,”,号或,“,*,”,号。边从,1,编号到,N,。,第一步，一条边被拿走；随后各步包括如下：,选择一条边,E,和连接着,E,的两个顶点,V1,和,V2,；,得到一个新的顶点，标记为,V1,与,V2,通过边,E,上的运算符运算的结果。,最后，游戏中没有边，游戏的得分为仅剩余的一个顶点的值。,样例,分析,分析,我们先枚举第一次删掉的边，然后再对每种状态进行动态规划求最大值 。,用,f(i,j,),表示从点,i,到点,j,进行删边操作所能得到的最大值，,num(i,),表示第,i,个顶点上的数，若为加法，那么：,进一步分析,最后，我们允许顶点上出现负数。以前的方程还适不适用呢？,这个例子的最优解应该是（,3+2,）*（,-10,）*（,-5,）,=250,，然而如果沿用以前的方程，得出的解将是（,-10,）*,3+2,）*（,-5,）,=125,。为什么？,我们发现，两个负数的积为正数；这两个负数越小，它们的积越大。我们从前的方程，只是尽量使得局部解最大，而从来没有想过负数的积为正数这个问题。,-10,3,2,-5,*,*,图六,+,分析,对于加法，两个最优相加肯定最优，而对于乘法,求最大值：,正数,正数，如果两个都是最大值，则结果最大,正数,负数，正数最小，负数最大，则结果最大,负数,负数，如果两个都是最小值，则结果最大,求最小值：,正数,正数，如果两个都是最小值，则结果最小,正数,负数，正数最大，负数最小，则结果最小,负数,负数，如果两个都是最大值，则结果最小,最终？,我们引入函数,fmin,和,fmax,来解决这个问题。,fmax(i,j,),表示从点,i,开始，到但,j,为止进行删边操作所能得到的最大值，,fmin(i,j,),表示最小值。,当,OP=,+,Fmax(i,j,)=maxfmax(i,k)+fmax(k+1,j),Fmin(i,j,)=minfmin(i,k)+fmin(k+1,j),当,OP=,*,完美解决,初始值,Fmax(i,i,)=,num(i,),Fmin(i,i,)=,num(i,),1=i=k=j=n,空间复杂度,:O(n,2,),时间复杂度,:,先要枚举每一条边为,O(n,),，然后动态规划为,O(n,3,),，因此总为,O(n,4,),。,棋盘分割,将一个,的棋盘进行如下分割：将原棋盘割下一块矩形棋盘并使剩下部分也是矩形，再将剩下的部分继续如此分割，这样割了,(n-1),次后，连同最后剩下的矩形棋盘共有,n,块矩形棋盘。,(,每次切割都只能沿着棋盘格子的边进行,),允许的分割方案 不允许的分割方案,任务：,棋盘上每一格有一个分值，一块矩形棋盘的,总分,为其所含各格分值之和。现在需要把棋盘按上述规则分割成,n,块矩形棋盘，并使各矩形棋盘总分的,均方差,最小。,均方差,：,算术平均值 ：,样例,输入,3,1 1 1 1 1 1 1 3,1 1 1 1 1 1 1 1,1 1 1 1 1 1 1 1,1 1 1 1 1 1 1 1,1 1 1 1 1 1 1 1,1 1 1 1 1 1 1 1,1 1 1 1 1 1 1 0,1 1 1 1 1 1 0 3,输出,1.633,均方差公式化简,分析,由化简后的均方差公式：,可知，均方差的平方为每格数的平方和除以,n,，然后减去平均值的平方，而后者是一个已知数。,因此，在棋盘切割的各种方案中，只需使得每个棋盘内各数值的平方和最小即可。,因此，我们需要求出各棋盘分割后的每个棋盘各数平方和的最小值，设为,w,，那么,答案为：,棋盘切割后的四种情况,动态规划,设,F(i,x,1,y,1,x,2,y,2,),表示以,x,1,y,1,x,2,y,2,为四边形对角线的棋盘切割成,k,块的各块数值总平方和的最小值，则有：,1=X1,x2,x3,x4=8,1=i=n,。,设棋盘边长为,m,则状态数为,nm,4,决策数最多,m,。,先预处理从左上角,(1,1),到右下角,(,i,j,),的棋盘和时间复杂度为,O(m,2,),，因此转移为,O(1),总时间复杂度为,O(nm,5,),。,总结,该类问题的基本特征是能将问题分解成为两两合并的形式。解决方法是对整个问题设最优值，枚举合并点，将问题分解成为左右两个部分，最后将左右两个部分的最优值进行合并得到原问题的最优值。有点类似分治的解题思想。,设前,i,到,j,的最优值，枚举剖分（合并）点，将,(,i,j,),分成左右两区间，分别求左右两边最优值，如下图。,状态转移方程的一般形式如下：,F(i,j,)=MaxF(i,k)+F(k+1,j)+,决策，,k,为划分点,