区间类型动态规划.ppt
《区间类型动态规划.ppt》由会员分享,可在线阅读,更多相关《区间类型动态规划.ppt(46页珍藏版)》请在咨信网上搜索。
1、区间类动态规划区间类动态规划央兢镀茸叼报镁摄垢坝痰猪终寻意熄蔼稻犊凛宴阀担墒徐咆核鳞颜迟剖趟区间类型动态规划区间类型动态规划合并类动态规划的特点合并类动态规划的特点合并:意思就是将两个或多个部分进行整合,当然合并:意思就是将两个或多个部分进行整合,当然也可以反过来,也就是是将一个问题进行分解成也可以反过来,也就是是将一个问题进行分解成两个或多个部分。两个或多个部分。特征:能将问题分解成为两两合并的形式特征:能将问题分解成为两两合并的形式求解:对整个问题设最优值,枚举合并点,将问题求解:对整个问题设最优值,枚举合并点,将问题分解成为左右两个部分,最后将左右两个部分的分解成为左右两个部分,最后将左
2、右两个部分的最优值进行合并得到原问题的最优值。有点类似最优值进行合并得到原问题的最优值。有点类似分治算法的解题思想。分治算法的解题思想。典型试题:整数划分,凸多边形划分、石子合并、典型试题:整数划分,凸多边形划分、石子合并、多边形合并、能量项链等。多边形合并、能量项链等。柄材犊捧夏他濒索掌晶冻兄室泌桂称卞氨指晃很硝挝蛆影拾齿火迪梯样竖区间类型动态规划区间类型动态规划整数划分整数划分给出一个长度为给出一个长度为n的数的数要在其中加要在其中加m-1个乘号,分成个乘号,分成m段段这这m段的乘积之和最大段的乘积之和最大mn=20有有T组数据,组数据,T=10000 换战有锗大幸厉斜赵艇恩寂涟蔽跑删纂韧
3、萍材羹贝验炼擞探肛厦钟毅峦滴区间类型动态规划区间类型动态规划贪心法贪心法尽可能平均分配各段,这样最终的数值将会尽可能大。但有尽可能平均分配各段,这样最终的数值将会尽可能大。但有反例。如反例。如191919分成分成3段段 19*19*19=6859但但191*91*9=156429,显然乘积更大。,显然乘积更大。将一个数分成若干段乘积后比该数小,因为输入数不超过将一个数分成若干段乘积后比该数小,因为输入数不超过20位,因此不需高精度运算。位,因此不需高精度运算。证明:证明:假设假设AB分成分成A和和B,且且A,BA*B(相当于相当于B个个A相加相加)同理可证明同理可证明A,B为任意位也成立为任意
4、位也成立剐胖伎溶寐冶要凄挽晓岳磁卜蘑谅早抑挚阁悦渊旭唾抿植综水砌刊魔匈脯区间类型动态规划区间类型动态规划动态规划动态规划可以先预处理出原数第可以先预处理出原数第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至于说输出,记录转
5、移的父亲就可以了。至于说输出,记录转移的父亲就可以了。联季捣榴尤仇墓侍蛙备靖蹭唉乍攫啪逾儡徊玩铜喂蹭凯氓疾弃尾辟姬寄氓区间类型动态规划区间类型动态规划石子合并 在一园形操场四周摆放在一园形操场四周摆放N堆石子堆石子(N100);现要将石子有次序地合并成一堆;现要将石子有次序地合并成一堆;规定每次只能选相临的两堆合并成一堆规定每次只能选相临的两堆合并成一堆,并将新的一并将新的一堆的石子数堆的石子数,记为该次合并的得分。记为该次合并的得分。选择一种合并石子的方案选择一种合并石子的方案,使得做使得做N-1次合并次合并,得得分的总和最少分的总和最少 选择一种合并石子的方案选择一种合并石子的方案,使得做
6、使得做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然而有更
7、好的方案:然而有更好的方案:第一次第一次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堆石子呢?堆
8、石子呢?不管怎么合并,总之最后总会归结为不管怎么合并,总之最后总会归结为2堆,如果我们把最后堆,如果我们把最后两堆分开,左边和右边无论怎么合并,都必须满足最优合两堆分开,左边和右边无论怎么合并,都必须满足最优合并方案,整个问题才能得到最优解。如下图:并方案,整个问题才能得到最优解。如下图:祥标覆坤界浸墨蝎菌墓丹造杏分免硬将无止墨抬阐慰蔷熟接根规业轴纂跑区间类型动态规划区间类型动态规划动态规划动态规划 设设ti,j表示从第表示从第i堆到第堆到第j堆石子数总和。堆石子数总和。Fmax(i,j)表示将从第表示将从第i堆石子合并到第堆石子合并到第j堆石子的最大的得分堆石子的最大的得分Fmin(i,j)
9、表示将从第表示将从第i堆石子合并到第堆石子合并到第j堆石子的最小的得分堆石子的最小的得分同理,同理,Fmaxi,i=0,Fmini,i=0时间复杂度为时间复杂度为O(n3)爷势警但僚僻佐毕煮遭韭酌英乡硷打纳蹿时招实愁堪硒诽太振合泛牧灸匈区间类型动态规划区间类型动态规划优化由于石子堆是一个圈,因此我们可以枚举分开的位置,首先由于石子堆是一个圈,因此我们可以枚举分开的位置,首先将这个圈转化为链,因此总的时间复杂度为将这个圈转化为链,因此总的时间复杂度为O(n4)。这样显然很高,其实我们可以将这条链延长这样显然很高,其实我们可以将这条链延长2倍,扩展成倍,扩展成2n-1堆,其中第堆,其中第1堆与堆与
10、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)或
11、者或者 (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+F
12、max 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堆石子的最小的得分堆石子的最小的得分同理,同
13、理,Fmaxi,i=0,Fmini,i=0时间复杂度为时间复杂度为O(n2)深庭竣锨酒湿倾黎樱胚虽锁止娄陪篮惕没柒林梗赂蛾沸怜闰沼而淀箔沛肄区间类型动态规划区间类型动态规划能量项链能量项链在在Mars星球上,每个星球上,每个Mars人都随身佩带着一串能量项链。人都随身佩带着一串能量项链。在项链上有在项链上有N颗能量珠。颗能量珠。能量珠是一颗有头标记与尾标记的珠子,这些标记对应着某能量珠是一颗有头标记与尾标记的珠子,这些标记对应着某个正整数。个正整数。对于相邻的两颗珠子,前一颗珠子的尾标记一定等于后一颗对于相邻的两颗珠子,前一颗珠子的尾标记一定等于后一颗珠子的头标记。如果前一颗能量珠的头标记为珠
14、子的头标记。如果前一颗能量珠的头标记为m,尾标记,尾标记为为r,后一颗能量珠的头标记为,后一颗能量珠的头标记为r,尾标记为,尾标记为n,则聚合后释,则聚合后释放的能量为放的能量为mrn(Mars单位),新产生的珠子的头标记单位),新产生的珠子的头标记为为m,尾标记为,尾标记为n。显然,对于一串项链不同的聚合顺序得到的总能量是不同的,显然,对于一串项链不同的聚合顺序得到的总能量是不同的,请你设计一个聚合顺序,使一串项链释放出的总能量最大。请你设计一个聚合顺序,使一串项链释放出的总能量最大。啄撅腑赋驱赁股纬阐饶吃讲钦垫杉靶额洪缆痪杖胡囱虽斌仓聪粕膊罐姿平区间类型动态规划区间类型动态规划分析样例:分
15、析样例: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颗珠子所能产颗珠
16、子所能产生的最大能量,则有:生的最大能量,则有: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个三角形顶点权值乘积之和最小?个三
17、角形顶点权值乘积之和最小?盈瘁拖筋梭袖痴亦陪志扑暴粟讯郎盎龋埂春告溜茸宜点甄狙拥词矗碍诗栏区间类型动态规划区间类型动态规划样例样例上述凸五边形分成上述凸五边形分成123,135,345三角形顶点权值乘积之和为:三角形顶点权值乘积之和为:121*122*123+121*123*231+123*245*231=12214884佑处捡乒枚渝烟苟颅秽参颗造莹骇尘撩叹僵咯藩拜侥寝祥室彦菲典笛治灼区间类型动态规划区间类型动态规划分析性质:一个凸多边形剖分一个三角形后,可以将凸性质:一个凸多边形剖分一个三角形后,可以将凸多边形剖分成三个部分:多边形剖分成三个部分:一个三角形一个三角形二个凸多边形(图二个凸多
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 区间 类型 动态 规划
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【天****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【天****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。