区间类型动态规划.ppt

区间类动态规划区间类动态规划央兢镀茸叼报镁摄垢坝痰猪终寻意熄蔼稻犊凛宴阀担墒徐咆核鳞颜迟剖趟区间类型动态规划区间类型动态规划合并类动态规划的特点合并类动态规划的特点合并：意思就是将两个或多个部分进行整合，当然合并：意思就是将两个或多个部分进行整合，当然也可以反过来，也就是是将一个问题进行分解成也可以反过来，也就是是将一个问题进行分解成两个或多个部分。两个或多个部分。特征：能将问题分解成为两两合并的形式特征：能将问题分解成为两两合并的形式求解：对整个问题设最优值，枚举合并点，将问题求解：对整个问题设最优值，枚举合并点，将问题分解成为左右两个部分，最后将左右两个部分的分解成为左右两个部分，最后将左右两个部分的最优值进行合并得到原问题的最优值。有点类似最优值进行合并得到原问题的最优值。有点类似分治算法的解题思想。分治算法的解题思想。典型试题：整数划分，凸多边形划分、石子合并、典型试题：整数划分，凸多边形划分、石子合并、多边形合并、能量项链等。多边形合并、能量项链等。柄材犊捧夏他濒索掌晶冻兄室泌桂称卞氨指晃很硝挝蛆影拾齿火迪梯样竖区间类型动态规划区间类型动态规划整数划分整数划分给出一个长度为给出一个长度为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 时间复杂度为时间复杂度为Omn2由于有由于有10000组数据，因此估计时间复杂度为组数据，因此估计时间复杂度为10000*203=8*107至于说输出，记录转移的父亲就可以了。至于说输出，记录转移的父亲就可以了。联季捣榴尤仇墓侍蛙备靖蹭唉乍攫啪逾儡徊玩铜喂蹭凯氓疾弃尾辟姬寄氓区间类型动态规划区间类型动态规划石子合并 在一园形操场四周摆放在一园形操场四周摆放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(n3)爷势警但僚僻佐毕煮遭韭酌英乡硷打纳蹿时招实愁堪硒诽太振合泛牧灸匈区间类型动态规划区间类型动态规划优化由于石子堆是一个圈，因此我们可以枚举分开的位置，首先由于石子堆是一个圈，因此我们可以枚举分开的位置，首先将这个圈转化为链，因此总的时间复杂度为将这个圈转化为链，因此总的时间复杂度为O(n4)。这样显然很高，其实我们可以将这条链延长这样显然很高，其实我们可以将这条链延长2倍，扩展成倍，扩展成2n-1堆，其中第堆，其中第1堆与堆与n+1堆完全相同，第堆完全相同，第i堆与堆与n+i堆完全相同，堆完全相同，这样我们只要对这这样我们只要对这2n堆动态规划后，枚举堆动态规划后，枚举f(1,n),f(2,n+1),f(n,2n-1)取最优值即可即可。取最优值即可即可。时间复杂度为时间复杂度为O(8n3),如下图：如下图：衡耪讶央掌爱函颁厚起础者囤僚寿导老漆却抽萨芬循梗红承宣霉误慷咨悼区间类型动态规划区间类型动态规划猜想猜想合并第合并第i堆到第堆到第j堆石子的最优断开位置堆石子的最优断开位置si,j要么等于要么等于i+1，要么等于，要么等于j-1，也就是说最优合并方案只可能，也就是说最优合并方案只可能是：是：(i)(i+1 j)或者或者 (i j-1)(j)哄烷瓤处侮覆亚眩科雕跑率凹真序习旭邯捞六刷亭徒谅蹦炎己宪夯谓柯乎区间类型动态规划区间类型动态规划证明设合并第设合并第i堆到第堆到第j堆石子的断开位置堆石子的断开位置 p，且，且ipj-1。设在。设在i,p之间存在一种断开方案之间存在一种断开方案q。如下图；。如下图；情况情况1：ti,ptp+1,j 合并方案合并方案1：(iq)(q+1.p)(p+1j)，它的，它的得分得分:F1=Fmax(i,q)+Fmax(q+1,p)+Fmax(p+1,j)+ti,j+ti,p合并方案合并方案2:(iq)(q+1.p)(p+1j)，它的得，它的得分：分：F2=Fmax i,q+Fmax q+1,p+Fmax p+1,j+ti,j+tq+1,j由于由于qp，所以，所以ti,ptp+1,jtq+1,j，所以，所以F1tp+1,j 与情况与情况1是对称。（证明略）是对称。（证明略）抓奎靛洒植缎由啼抑躺按岩曹熏态爬勿贬运附硒拳醇皖扦令曙谊格孕酉葛区间类型动态规划区间类型动态规划状态转移方程设设ti,j表示从第表示从第i堆到第堆到第j堆石子数总和。堆石子数总和。Fmax(i,j)表示将从第表示将从第i堆石子合并到第堆石子合并到第j堆石子的最大的得分堆石子的最大的得分Fmin(i,j)表示将从第表示将从第i堆石子合并到第堆石子合并到第j堆石子的最小的得分堆石子的最小的得分同理，同理，Fmaxi,i=0，Fmini,i=0时间复杂度为时间复杂度为O(n2)深庭竣锨酒湿倾黎樱胚虽锁止娄陪篮惕没柒林梗赂蛾沸怜闰沼而淀箔沛肄区间类型动态规划区间类型动态规划能量项链能量项链在在Mars星球上，每个星球上，每个Mars人都随身佩带着一串能量项链。人都随身佩带着一串能量项链。在项链上有在项链上有N颗能量珠。颗能量珠。能量珠是一颗有头标记与尾标记的珠子，这些标记对应着某能量珠是一颗有头标记与尾标记的珠子，这些标记对应着某个正整数。个正整数。对于相邻的两颗珠子，前一颗珠子的尾标记一定等于后一颗对于相邻的两颗珠子，前一颗珠子的尾标记一定等于后一颗珠子的头标记。如果前一颗能量珠的头标记为珠子的头标记。如果前一颗能量珠的头标记为m，尾标记，尾标记为为r，后一颗能量珠的头标记为，后一颗能量珠的头标记为r，尾标记为，尾标记为n，则聚合后释，则聚合后释放的能量为放的能量为mrn（Mars单位），新产生的珠子的头标记单位），新产生的珠子的头标记为为m，尾标记为，尾标记为n。显然，对于一串项链不同的聚合顺序得到的总能量是不同的，显然，对于一串项链不同的聚合顺序得到的总能量是不同的，请你设计一个聚合顺序，使一串项链释放出的总能量最大。请你设计一个聚合顺序，使一串项链释放出的总能量最大。啄撅腑赋驱赁股纬阐饶吃讲钦垫杉靶额洪缆痪杖胡囱虽斌仓聪粕膊罐姿平区间类型动态规划区间类型动态规划分析样例：分析样例：N=4，4颗珠子的头标记与尾标记依次为颗珠子的头标记与尾标记依次为(2，3)(3，5)(5，10)(10，2)。我们用记号我们用记号 表示两颗珠子的聚合操作，释放总能量：表示两颗珠子的聚合操作，释放总能量：(4 1)2)3）=10*2*3+10*3*5+10*5*10=710主蒙二箱式拎幻厂由绥杆窟猴痰窜纪腰撞备匹陈禹搀垛窗握项承蓬独蛔趣区间类型动态规划区间类型动态规划动态规划该题与石子合并完全类似。该题与石子合并完全类似。设链中的第设链中的第i颗珠子头尾标记为颗珠子头尾标记为(Si-1与与Si)。令令F(i,j)表示从第表示从第i颗珠子一直合并到第颗珠子一直合并到第j颗珠子所能产颗珠子所能产生的最大能量，则有：生的最大能量，则有：F(i,j)=MaxF(i,k)+F(k+1,j)+Si-1*Sk*Sj,i=kj边界条件：边界条件：F(i,i)=01=ikj=n至于圈的处理，与石子合并方法完全相同，时间复至于圈的处理，与石子合并方法完全相同，时间复杂度杂度O(8n3)。做丫爵臂虞黍谱桥省殆诣耍游食车涡务血别级串谁兜助归始逻兜喉吏葛胚区间类型动态规划区间类型动态规划凸多边形的三角剖分凸多边形的三角剖分给定由给定由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*ak1=ikj=n时间复杂度时间复杂度O(n3)碴荫航篓缴谦勿慢娟置破内求氏阉摧银扑京疵刀胯增逊到雏互秽环耗甥辊区间类型动态规划区间类型动态规划讨论为什么可以不考虑这种情况？为什么可以不考虑这种情况？见癸弧珊守估辩踢比疽井筋婶帆墟桶姿六恕汁祟尖宣梢刨降蠕疟惹盖醒流区间类型动态规划区间类型动态规划可以看出图可以看出图1和图和图2是等价的，也就是说如果存是等价的，也就是说如果存在图在图1的剖分方案，则可以转化成图的剖分方案，则可以转化成图2的剖分的剖分方案，因此可以不考虑图方案，因此可以不考虑图1的这种情形。的这种情形。舀驹奸祝露矣演班罐堑垦坪展胶性及九焰泉硅染文摇禁坑侗斩帕末趣铃棍区间类型动态规划区间类型动态规划多边形（多边形（IOI98IOI98）多多角角形形是是一一个个单单人人玩玩的的游游戏戏，开开始始时时有有一一个个N N个个顶顶点点的的多多边边形形。如如图图，这这里里N=4N=4。每每个个顶顶点点有有一一个个整整数数标标记记，每每条条边边上上有有一一个个“+”号号或或“*”号号。边边从从1 1编号到编号到N N。第第一一步步，一一条条边边被被拿拿走走；随随后后各各步步包包括如下：括如下：选选择择一一条条边边E E和和连连接接着着E E的的两两个个顶顶点点V1V1和和 V2V2；得得到到一一个个新新的的顶顶点点，标标记记为为V1V1与与V2V2通通过过边边E E上的运算符运算的上的运算符运算的结结果。果。最最后后，游游戏戏中中没没有有边边，游游戏戏的的得得分分为为仅仅剩余的一个顶点的值。剩余的一个顶点的值。葬端泻伯理权尾厉彰夜凯巩蚁秆貌紧筹卤音冬垄瞳人抢酸处饮烹立蔷苍史区间类型动态规划区间类型动态规划样例分析 缅左投菠哥厦楷那贼鸯澈爆贿惋伙谗狙甚罗人颧勋侗揽貌辣恬洞蓑骚梅湍区间类型动态规划区间类型动态规划分析我们先枚举第一次删掉的边，然后再对每种状态进行动态规划求最大值。用f(i,j)表示从点i到点j进行删边操作所能得到的最大值，num(i)表示第i个顶点上的数，若为加法，那么：梭膀蜜止慌贰流脂浩姜留沸救肛耙帜教粱队洋巩永睡详孕歇暂针诵魔烂圭区间类型动态规划区间类型动态规划进一步分析最后，我们允许顶点上出现负数。以前的方程还适不适用最后，我们允许顶点上出现负数。以前的方程还适不适用呢？呢？这这个个例例子子的的最最优优解解应应该该是是（3+23+2）*（-10-10）*（-5-5）=250=250，然然而而如如果果沿沿用用以以前前的的方方程程，得得出出的的解解将将是是（-10-10）*3+23+2）*（-5-5）=125=125。为什么？。为什么？我们发现，两个负数的积为正数；这两个负数越小，它们我们发现，两个负数的积为正数；这两个负数越小，它们的积越大。我们从前的方程，只是尽量使得局部解最大，的积越大。我们从前的方程，只是尽量使得局部解最大，而从来没有想过负数的积为正数这个问题。而从来没有想过负数的积为正数这个问题。-1032-5*图六+另它眠咒铺一醉谐扇搜恬箩妮冗伴买援则渺环弄攀芜项丝俐虽弊浸吗布穗区间类型动态规划区间类型动态规划分析分析对于加法，两个最优相加肯定最优，而对于乘法对于加法，两个最优相加肯定最优，而对于乘法求最大值：求最大值：正数正数正数，如果两个都是最大值，则结果最大正数，如果两个都是最大值，则结果最大正数正数负数，正数最小，负数最大，则结果最大负数，正数最小，负数最大，则结果最大负数负数负数，如果两个都是最小值，则结果最大负数，如果两个都是最小值，则结果最大求最小值：求最小值：正数正数正数，如果两个都是最小值，则结果最小正数，如果两个都是最小值，则结果最小正数正数负数，正数最大，负数最小，则结果最小负数，正数最大，负数最小，则结果最小负数负数负数，如果两个都是最大值，则结果最小负数，如果两个都是最大值，则结果最小住抉蛀田瞪众迹责谊邹就烦纯盼绞饭犁凌圾忆蓉腋紊壕驰缀肌烈驯蛙炼免区间类型动态规划区间类型动态规划最终？我们引入函数我们引入函数fminfmin和和fmaxfmax来解决这个问题。来解决这个问题。fmax(i,j)fmax(i,j)表示从点表示从点i i开始，到但开始，到但j j为止进行删为止进行删边操作所能得到的最大值，边操作所能得到的最大值，fmin(i,j)fmin(i,j)表示最表示最小值。小值。当当OP=OP=+Fmax(i,j)=maxfmax(i,k)+fmax(k+1,j)Fmax(i,j)=maxfmax(i,k)+fmax(k+1,j)Fmin(i,j)=minfmin(i,k)+fmin(k+1,j)Fmin(i,j)=minfmin(i,k)+fmin(k+1,j)恒钢钳坯院宠萨拎驳厘刘制荐宅返慌嘲驻羔眺波兢锗怎艇拼需好雾亨干外区间类型动态规划区间类型动态规划当当OP=OP=*邹仕掌履梦事碰萝驻楷狮评攒磺昆梯巨捕巴掷炔炭呆佯杰吮壁宾道沤处质区间类型动态规划区间类型动态规划完美解决初始初始值值 Fmax(i,i)=num(i)Fmax(i,i)=num(i)Fmin(i,i)=num(i)Fmin(i,i)=num(i)1=i=k=j=n1=i=k=D2,只要证明只要证明d(1,3)+d(2,4)d(1,2)+d(3,4)连接两边，见图连接两边，见图3，由三角形的三边关系定理即可证明。，由三角形的三边关系定理即可证明。赚撤芒痘起掖佃烽阴圈巍锯倡孽渝昆擂窑如疽句总蚤夏惩宛晕摸文赌暮款区间类型动态规划区间类型动态规划分析结论：青蛙在结论：青蛙在1号结点只能跳到号结点只能跳到2号结点或者号结点或者n号结点。号结点。如果青蛙跳到了如果青蛙跳到了2号结点，则问题转化为：从号结点，则问题转化为：从2出发，遍历出发，遍历2.n一次仅一次仅一次的最短距离。一次的最短距离。如果青蛙跳到了如果青蛙跳到了n号结点，则问题转化为：从号结点，则问题转化为：从n出发，遍历出发，遍历2.n一次仅一次仅一次的最短距离。一次的最短距离。这实际上是递归的思维，把问题转化为了本质相同但规模更这实际上是递归的思维，把问题转化为了本质相同但规模更小的子问题小的子问题,如下图。如下图。领衔盈东抹苔搬暇辑猩滓跌夫憾渠皑奖釜准螟架硷先拽丘材蔓阳黍迹峪囊区间类型动态规划区间类型动态规划动态规划(1)f(s,L,0)表示从表示从s出发，遍历出发，遍历s.s+L-1一次且仅一次的最短距离一次且仅一次的最短距离;f(s,L,1)表示从表示从s+L-1出发，遍历出发，遍历s.s+L-1一次且仅一次的最短一次且仅一次的最短距离。状态转移方程为：距离。状态转移方程为：状态总数为状态总数为n2，状态转移的复杂度为，状态转移的复杂度为O(1)，总的时间复杂度为，总的时间复杂度为O(n2)。曹皖箩健黍戳菇惰映社蛰让娇莲八才措萎睡弱摩藤严事淘滇昏乔甭卯苟撞区间类型动态规划区间类型动态规划动态规划(2)F(i,j,0)表示还有表示还有ij号点没访问号点没访问,且青蛙停在且青蛙停在i的最小值的最小值F(i,j,1)表示还有表示还有ij号点没访问号点没访问,且青蛙停在且青蛙停在j的最小值的最小值状态总数为状态总数为n2，状态转移的复杂度为，状态转移的复杂度为O(1)，总的时间复杂度为，总的时间复杂度为O(n2)。绣故拧蹭晴跪铡娘栓克济疵访蠢侍驶惭汐捍雁萌匆腻茫艳掳延铀沈拱藻铂区间类型动态规划区间类型动态规划主程序for i:=1 to n do for j:=n downto i+1 do begin update(fi+1,j,0,fi,j,0+di,i+1);/停在i,跳到i+1 update(fi+1,j,1,fi,j,0+di,j);/停在i,跳到j update(fi,j-1,0,fi,j,1+di,j);/停在j,跳到i update(fi,j-1,1,fi,j,1+dj-1,j);/停在j,跳到j-1 end;雏锨盖铺横煮褐彝莹摹滋烈瓤们诌需军猎乍猩场辕脾伐伴活甫蹿暮萧园米区间类型动态规划区间类型动态规划棋盘分割棋盘分割 将一个将一个的棋盘进行如下分割：将原棋盘割下一块矩形的棋盘进行如下分割：将原棋盘割下一块矩形棋盘并使剩下部分也是矩形，再将剩下的部分继续如此分棋盘并使剩下部分也是矩形，再将剩下的部分继续如此分割，这样割了割，这样割了(n-1)次后，连同最后剩下的矩形棋盘共有次后，连同最后剩下的矩形棋盘共有n块矩形棋盘。块矩形棋盘。(每次切割都只能沿着棋盘格子的边进行每次切割都只能沿着棋盘格子的边进行)允许的分割方案允许的分割方案 不允许的分割方案不允许的分割方案哟幕到澎酣轧羌仲凳砍魁啪翌稗击镍目好啮糟雇飘惮倍疾瓮谓孵蚀辆霍牧区间类型动态规划区间类型动态规划任务：任务：棋盘上每一格有一个分值，一块矩形棋盘的棋盘上每一格有一个分值，一块矩形棋盘的总总分分为其所含各格分值之和。现在需要把棋盘按为其所含各格分值之和。现在需要把棋盘按上述规则分割成上述规则分割成n块矩形棋盘，并使各矩形棋块矩形棋盘，并使各矩形棋盘总分的盘总分的均方差均方差最小。最小。均方差均方差：算术平均值算术平均值：讫酶必扯裴嘱僚跺想姜钉冻得私觅缆执钳申告骋吱郊潞便南迫芬屑崔与枉区间类型动态规划区间类型动态规划样例 输入输入31 1 1 1 1 1 1 31 1 1 1 1 1 1 11 1 1 1 1 1 1 11 1 1 1 1 1 1 11 1 1 1 1 1 1 11 1 1 1 1 1 1 11 1 1 1 1 1 1 01 1 1 1 1 1 0 3输出输出1.633嘿值小尝琴拜敞茵尤宏厨弦宝搅试呀希墟礁拢刃愈烙伶梁瓮劈蚜腥疯淑渐区间类型动态规划区间类型动态规划均方差公式化简均方差公式化简毋姚韩妮址蹲别聪蓉耘厦雾诽睁层抉恶镐伺驴潍募泻见尖定漾号榨异敦品区间类型动态规划区间类型动态规划分析 由化简后的均方差公式：由化简后的均方差公式：可知，均方差的平方为每格数的平方和除以可知，均方差的平方为每格数的平方和除以n，然后，然后减去平均值的平方，而后者是一个已知数。减去平均值的平方，而后者是一个已知数。因此，在棋盘切割的各种方案中，只需使得每个棋盘因此，在棋盘切割的各种方案中，只需使得每个棋盘内各数值的平方和最小即可。内各数值的平方和最小即可。因此，我们需要求出各棋盘分割后的每个棋盘各数平因此，我们需要求出各棋盘分割后的每个棋盘各数平方和的最小值，设为方和的最小值，设为w，那么，那么答案为：答案为：泳辣膳械底揉盐镑饵悄苹按琼陷倪侗呕老耶鉴御趾阶潘柄食俺速淮秋前颂区间类型动态规划区间类型动态规划棋盘切割后的四种情况浪嫡惭并蔬蜜兼尧毫戎胞独庆份莆戒瓜殷笼垦虞爬抬徽秸乒片了混止既卤区间类型动态规划区间类型动态规划动态规划动态规划设设F(i,x1,y1,x2,y2)表示以表示以x1,y1x2,y2为四边形对角为四边形对角线的棋盘切割成线的棋盘切割成k块的各块数值总平方和的最小值，块的各块数值总平方和的最小值，则有：则有：1=X1,x2,x3,x4=8,1=i=n。设棋盘边长为设棋盘边长为m,则状态数为则状态数为nm4,决策数最多决策数最多m。先预处理从左上角先预处理从左上角(1,1)到右下角到右下角(i,j)的棋盘和时间的棋盘和时间复杂度为复杂度为O(m2)，因此转移为，因此转移为O(1),总时间复杂度为总时间复杂度为O(nm5)。介撅誉腔知四溜梢跑肌鸳董鼻溶矮诽仿左怂柿缀惶璃笆妒歪此汗确贤岿厚区间类型动态规划区间类型动态规划总结总结该类问题的基本特征是能将问题分解成为两两合并的形式。该类问题的基本特征是能将问题分解成为两两合并的形式。解决方法是对整个问题设最优值，枚举合并点，将问题分解决方法是对整个问题设最优值，枚举合并点，将问题分解成为左右两个部分，最后将左右两个部分的最优值进行解成为左右两个部分，最后将左右两个部分的最优值进行合并得到原问题的最优值。有点类似分治的解题思想。合并得到原问题的最优值。有点类似分治的解题思想。设前设前i到到j的最优值，枚举剖分（合并）点，将的最优值，枚举剖分（合并）点，将(i,j)分成左右分成左右两区间，分别求左右两边最优值，如下图。两区间，分别求左右两边最优值，如下图。状态转移方程的一般形式如下：状态转移方程的一般形式如下：F(i,j)=MaxF(i,k)+F(k+1,j)+决策，决策，k为划分点为划分点缘法雁穴蛀败香它堪伦鞠炬冲妓食证笔诺峪忍寝摊儡闽祈扯箩们沂转颗篱区间类型动态规划区间类型动态规划