资源预览内容
第1页 / 共35页
第2页 / 共35页
第3页 / 共35页
第4页 / 共35页
第5页 / 共35页
第6页 / 共35页
第7页 / 共35页
第8页 / 共35页
第9页 / 共35页
第10页 / 共35页
亲,该文档总共35页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
区间类动态规划长沙市雅礼中学 朱全民整数划分 给出一个长度为n的数 要在其中加m-1个乘号,分成m段 这m段的乘积之和最大 mA*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 时间复杂度为Om2n 由于有10000组数据,因此估计时间复杂度为 10000*203=8*107 至于说输出,记录转移的父亲就可以了。石子合并 l 在一园形操场四周摆放N堆石子(N100); l 现要将石子有次序地合并成一堆; l 规定每次只能选相临的两堆合并成一堆,并将新的 一堆的石子数,记为该次合并的得分。 1. 选择一种合并石子的方案,使得做N-1次合并, 得分的总和最少 2. 选择一种合并石子的方案,使得做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),如下图:能量项链 在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颗珠子头尾标记为(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)=0 1=ikj=n 至于圈的处理,与石子合并方法完全相同,时间 复杂度O(8n3) 。凸多边形的三角剖分 给定由N顶点组成的凸多边形 每个顶点具有权值 将凸N边形剖分成N-2个三角形 求N-2个三角形顶点权值乘积之和最小? 样例上述凸五边形分成123 , 135, 345三角形顶点权值乘积之和为: 121*122*123+121*123*231+123*245*231= 12214884分析性质:一个凸多边形剖分一个三角形后,可以将 凸多边形剖分成三个部分: u一个三角形 u二个凸多边形(图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(n3)讨论为什么可以不考虑这种情况? 可以看出图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。为什么? 我们发现,两个负数的积为正数;这两个负数越小,它 们的积越大。我们从前的方程,只是尽量使得局部解最 大,而从来没有想过负数的积为正数这个问题。 -1032-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(n2) 时间时间 复杂杂度:先要枚举举每一条边为边为 O(n), 然后动态规动态规 划为为O(n3 ),因此总为总为 O(n4) 。棋盘分割 将一个的棋盘进行如下分割:将原棋盘割下一块矩 形棋盘并使剩下部分也是矩形,再将剩下的部分继续如此 分割,这样割了(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,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为划分点
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号