《杨沐浅析信息学中的分与合.ppt》由会员分享，可在线阅读，更多相关《杨沐浅析信息学中的分与合.ppt（27页珍藏版）》请在三一文库上搜索。
1、浅析信息学中的“分”与“合”,福建省福州第三中学 杨沐,仇绚敌舀警参锥旦抛一矮镜简蝗亥要快君芍派鞍比泼衷犬秧叫命蜜坦杆锌杨沐浅析信息学中的分与合杨沐浅析信息学中的分与合,引言,分 “分”的思想是将一个难以直接解决的大问题，转化成一些规模较小或限制某些条件的子问题来思考，以求将问题解决。,合 “合”的思想与“分”相对，是将一些零散的小问题的解决合并成一个大问题，从而取得整个问题的解决。,话说天下大势，合久必分，分久必合,机吵赢蔓比厚躇生枣蝎弗昔慌蘑一刚姐第婚侍梭霄馆佑珠疚摄捣烦酉伤磋杨沐浅析信息学中的分与合杨沐浅析信息学中的分与合,引言,例一牛奶模版 例二树的重建 例三最优序列,二分 化归,运用
2、“分”与“合”思想方法解题的精髓在于通过在“分”与“合”之间的转化，找出解决问题的关键，从而解决问题。 “分治法”是运用“分”与“合”思想方法解题的重要应用，此外，“分”与“合”的思想方法还有更多、更广泛的应用。,N,K限制下最优化问题N,K,Len限制下存在性问题,规模为n的问题规模为n-1的问题,锄御狂芥绩将倾豺葱分肿瓤秤勿炭吧秃秽镶峻蚜沂伺缀壬编以找皆荫澄炳杨沐浅析信息学中的分与合杨沐浅析信息学中的分与合,例三最优序列,给定一个长度为N的正整数序列。 求一个子序列，使得原序列中任意长度为M的子串中被选出的元素不超过K个。 要求选出的元素之和最大。 数据范围： 1N1000 1K，M100
3、,镐拿肖虱沉辆厚兽命报藻攒囚俩野讯微萄狄贴吹澜红掷鸥综溃盐畜削戎忽杨沐浅析信息学中的分与合杨沐浅析信息学中的分与合,例三最优序列,输入数据： N=10，M=4，K=2 7，3，4，8，2，6，5，7，4，8 输出答案： 36 7，3，4，8，2，6，5，7，4，8,拇殴懂狞邯走稼鹃元欺侗焰返坦碗揭窒惜恒放停拷杯冻蘑靶拜土快厨粮固杨沐浅析信息学中的分与合杨沐浅析信息学中的分与合,例三最优序列分析,动态规划 线段树？ 怎么办？,“分”,超时,无从入手,O(2MN)！,O(21001000),嗡晚屑拇园赢窝衰毖武巷木问怂筛治嚣刨柯镜碾丘唾岂搐喻难束丈材圈沁杨沐浅析信息学中的分与合杨沐浅析信息学中的分
4、与合,例三最优序列“分”繁为简,动态规划之所以不可行，原因在于题目中K和M的范围太大了！ 利用“分”的思想，我们尝试限制K，令K=1，也就是对于长度为M的子串，最多只选一个元素作为原题的一个子问题：,蚤暇倍袁湛府孩仲耘撑蔑谭人原芬青雄币优管酌哑伟郧蝶隶渠施灿俗缄涨杨沐浅析信息学中的分与合杨沐浅析信息学中的分与合,例三最优序列子问题,给定一个长度为N的正整数序列。 求一个子序列，使得原序列中任意长度为M的子串中被选出的元素不超过1个。 要求选出的元素之和最大。 数据范围： 1N1000 1M100,驮架灼逃短扩捉盟判状秤愁助寐宿匠辽蚀鸭龄乎赢亲虫狈岔襄汲孪剩章严杨沐浅析信息学中的分与合杨沐浅析信
5、息学中的分与合,例三最优序列“分”繁为简,对于这个子问题，由于K做了限制，我们可以用动态规划来解决这个问题。 设dpi表示前i个元素，在满足题意的前提下选出的最大和 dpi=max(dpi-1,dpi-M+valuei) iM dpi=max(dpi-1,valuei) 0iM dp0=0,荡手驶确埠执戍鼓益妓妊冷赐土惹熙迸芭砸抽软鸵潍乓杭洞迸于轩卤殴绒杨沐浅析信息学中的分与合杨沐浅析信息学中的分与合,例三最优序列进一步分析,子问题,原问题,是否可以通过求解K次的子问题从而解决原题呢?,1,K,莽豆振吕视央误帧斩晨拐肄门驱馋孤珐扁只瞧扬蒲偏养咨航都砾感斡和虹杨沐浅析信息学中的分与合杨沐浅析信息
6、学中的分与合,例三最优序列进一步分析,命题 原问题的解集等价于由K组互不相交的子问题的解组成的解集。 引理一 原问题的任意一组解都可以由K组不相交的子问题的解组成。 引理二 任意K组不相交的子问题的解的并均为原问题的解。,骗汛逮悠腔弗恒尺囤碑惨遇恬徐悼针猫脏跺颓觅辈隶持嚷劝讫牛锅墓阀汗杨沐浅析信息学中的分与合杨沐浅析信息学中的分与合,引理一 原问题的任意一组解都可以由K组不相交的子问题的解组成。 证明 对于原问题的任意一解P=a1,a2,a3at，a1a2a3at。设sumi表示该解在区间1,i内取出的元素个数，则根据题意满足不等式： sumi-sumi-MK,饺瞥锨蒙臆伤娩罗畏逢涕瓜鹏练肝干
7、介眩悯铣野圾建乓吗鸣游胖法术止概杨沐浅析信息学中的分与合杨沐浅析信息学中的分与合,以下，我们给出一种构造法使之能产生一组与该解等价的K个子问题的解。 设K个子问题的解分别为P0,P1,P2Pk-1， 令Pi=aj | ji (mod K) sumi-sumi-MK ai-ai-kM P0,P1,P2Pk-1均为合法的子问题的解 又因为P0P1P2Pk-1=P，因此我们成功地构造出了子问题的解。,赖村邮敷漫栽媒短诀文坠篷构哑贵冠瞩沫朱嗓授敏讫臭猿痞妙凯使泌汝韶杨沐浅析信息学中的分与合杨沐浅析信息学中的分与合,引理二 任意K组不相交的子问题的解的并均为原问题的解。 证明 设K个子问题的不相交的解分
8、别为P0,P1,P2Pk-1 ， Pi=ai1,ai2,ai3ail，ai1ai2ai3ail 对于任意长度为M的区间，Pi至多只有一个元素在其内部,谓亲希迷诲棠线环幅氓急串呐裸迹馏罪春佬歹恕翔矗健指吝甲贺匪才齐垢杨沐浅析信息学中的分与合杨沐浅析信息学中的分与合,设P=P0P1P2Pk-1， 则对于任意长度为M的区间，P在其内部选出的元素个数不超过K个 任意K组互不相交的子问题的解的并都是原问题的合法解。 引理一与引理二分别证明了命题的充分性和必要性，因此该命题成立,拣况泞堰炎揪柯蔽蔡挺氰破纫锄龄仅我鹿扇满篱绣跟奉镭姜舶视湖弧蒸宫杨沐浅析信息学中的分与合杨沐浅析信息学中的分与合,例三最优序列进
9、一步分析,题目中存在着一个潜条件，即： 每个元素只能被选一次 若直接套用K次动态规划来求解，有可能导致某个元素被取多次，无法满足题目中的这个条件。,煌轻压草赦们傲撑呸摆戍孵施盟磨得旗俯寞充抠释小镇滥鬃罗陈汇拌腺地杨沐浅析信息学中的分与合杨沐浅析信息学中的分与合,例三最优序列进一步分析,N=10，M=4，K=2 3 3 3 3 动态规划：12 贪心：9,标准答案：10,1,1,1,1,1,1,1,1,3,3,并 1 3 1 3 1,并 1 3 1 1 3 1,辟抡冲咙湃惮奏域前删驾刀笑客箔纷铸肋煽垣七它演梁溉涧杜逼玫韦禁云杨沐浅析信息学中的分与合杨沐浅析信息学中的分与合,考虑动态规划与贪心之所以
10、不能得到正确解，其关键原因在于题目中存在着一个元素只能被取一次的限制，而对于这种限制各点被选取次数的题目，我们通常使用网络流来解决，那么这道题是否也能通过转化图论模型来使用网络流解决呢？答案是肯定的。,例三最优序列整体分析,慌火向蓑洽暂削俊织竭负醋遁溜谈酚厨救包郡檬倍学涨消鼠迈竣哄水琉独杨沐浅析信息学中的分与合杨沐浅析信息学中的分与合,例三最优序列整体分析,构造带权网络G=(V,A,C) 序列中的每个元素i用顶点i与i表示，ii连边，容量为1，费用为该元素的数值valuei，图中包含源S与汇T。 所有点i向点(i+1)连边，容量为+ ，费用为0 源S向所有点i各连一条边，容量为+，费用为0 所
11、有点i向汇T各连一条边，容量为+，费用为0 所有点i向点(i+M)连边，容量为+ ，费用为0,顾膨娱臆诅薯振愤焦硼慷亿吟踪邓把赔瞄揽哲豌垂酿侨雄枢灸廷区包系糜杨沐浅析信息学中的分与合杨沐浅析信息学中的分与合,3,2,1,n,1,2,3,n,T,S,容量 = 1 费用 = valuei,容量 = + 费用 = 0,僵斤邮拆醉卜耐蕊完喉珠瘁沛海挺维咀崇摹鲁埋菲舌设寻巢膜恼综划筏戴杨沐浅析信息学中的分与合杨沐浅析信息学中的分与合,例三最优序列整体分析,构图完成之后，网络中的每个单位流量表示一个子问题的解，因此，我们只需要在网络中寻找K次最大费用增广路即可得到答案。 由于这张图的边数与顶点数同阶，若使
12、用SPFA算法求增广轨，则期望时间复杂度仅为O(KN)，是个十分优秀的算法。,拐盯级垢寡娃织堪痊很蝎雷铡非企馅突突萌铸阀熊膳量沿来碳黔底臣憋嗣杨沐浅析信息学中的分与合杨沐浅析信息学中的分与合,总结,分,合,对立,统一,辨证关系,分中有合，合中有分,转化,“分”的思想帮助我们迅速地切入问题核心，但若过分细化则会使问题太过凌乱，失去求解的方向；而“合”的思想则以线串珠，使各种纷杂无序的问题具有了整体性。,善于归纳总结,勇于创新,彤遭莲顺逗伶魂赵球驱轮运素吊洁章克韵面渝缘采疡崖梢瘫恒园顾帮株彝杨沐浅析信息学中的分与合杨沐浅析信息学中的分与合,谢 谢,馋窘滥财挡哇贪舍磐够焕浅介礁蜒勇简块搬佣据胚锌斜员
13、价圭体奖周鳖期杨沐浅析信息学中的分与合杨沐浅析信息学中的分与合,总结：“分”与“合”虽然对立，却没有明显的分界。一道问题若使用“分”的方法，则必然有“合”的操作，正所谓“分中有合，合中有分”，这两者相互对立，各有优势，却又相互补充，“分”的思想帮助我们迅速地切入问题核心，但若过分细化则会使问题太过凌乱，失去求解的方向；而“合”的思想则以线串珠，使各种纷杂无序的问题具有了整体性，这正体现了两者之间的辨证关系。 运用“分”与“合”的思想，对于不同的题目需要不同的分析，其精髓就在于“转化”。无论是“分”还是“合”都是朝着将问题转化为更加便于思考的方向前进，而在这路途中，又需要我们善于归纳总结。只有将
14、已有的知识与“分合”思想有机地结合起来，同时勇于创新，不断积累经验，我们才能从千变万化的题目中找寻出本质，从而更快更有效地解决实际问题。,和舟路厦逸塔纸宫其方馋怔样叛燃挠枣化毅肘筛镐兼琶疚蔡回谅泞窝斯沃杨沐浅析信息学中的分与合杨沐浅析信息学中的分与合,整体,部分,网络流！,转化目标,动态规划,贪心,小结,萎焊厩孩锦催地尝阶研狭栋痔锻见已钢妹橇鼻具剿酣英瑶纱魁紊转祸龟嗣杨沐浅析信息学中的分与合杨沐浅析信息学中的分与合,线段树无法解决该题的原因,因为原问题是要求对于任意长度为M的区间，都限制了取数不超过K个。而这些区间有互相有交，这使得线段树很难准确的表示一个状态并进行处理。 更重要的是，线段树只是一个用来提升算法效率的辅助工具，若要使用线段树，则必须先提出一个可行的算法。但对于这题我们很难想出一个可以使用线段树的算法。,心乞劈座尉蛾刽桐蹋茬墙脖怕到环容烩渴魔翼总疮哇闻渍疗掀脱寂匠厌逃杨沐浅析信息学中的分与合杨沐浅析信息学中的分与合,动态规划的解法,将连续M位的被选状态(0,1)压缩成M位二进制数表示,DPi,j表示1,i区间,最后M位状态为j时的最优解,由于满足无后效性和最优子结构性质,可以使用动态规划解决,转移方程如下:,萄谜媒擒斗西扶瘤氰尖洗殷阵惮瓦谆肿链档余办拐深记丈颧尽托授融短酉杨沐浅析信息学中的分与合杨沐浅析信息学中的分与合,