浅析信息学中的分与合课件

《浅析信息学中的分与合课件》由会员分享，可在线阅读，更多相关《浅析信息学中的分与合课件（27页珍藏版）》请在装配图网上搜索。

1、福建省福州第三中学福建省福州第三中学杨沐杨沐引言引言v分v“分分”的思想是将的思想是将一个难以直接解决一个难以直接解决的大问题，转化成的大问题，转化成一些规模较小或限一些规模较小或限制某些条件的子问制某些条件的子问题来思考，以求将题来思考，以求将问题解决。问题解决。v合v“合合”的思想与的思想与“分分”相对，是将相对，是将一些零散的小问题一些零散的小问题的解决合并成一个的解决合并成一个大问题，从而取得大问题，从而取得整个问题的解决。整个问题的解决。引言引言v例一例一牛奶模版牛奶模版v例二例二树的重建树的重建v例三例三最优序列最优序列二分二分化归化归v运用运用“分分”与与“合合”思想思想方法方法

2、解题的精髓在解题的精髓在于通过在于通过在“分分”与与“合合”之间的转化之间的转化，找出找出解决问题的关键，从而解决问题。解决问题的关键，从而解决问题。“分治法分治法”是是运用运用“分分”与与“合合”思想方法解题的重要思想方法解题的重要应用，此外，应用，此外，“分分”与与“合合”的思想方法还的思想方法还有更多、更广泛的应用。有更多、更广泛的应用。N,K限制下最优化问题限制下最优化问题N,K,Len限制下存在性问题限制下存在性问题规模为规模为n的问题的问题规模为规模为n-1的问题的问题例三例三最优序列最优序列v给定一个长度为给定一个长度为N的正整数序列。的正整数序列。v求一个子序列，使得原序列中任

3、意长度为求一个子序列，使得原序列中任意长度为M的子串中被选出的元素不超过的子串中被选出的元素不超过K个。个。v要求选出的元素之和最大。要求选出的元素之和最大。v数据范围：数据范围：1N10001K，M100例三例三最优序列最优序列v输入数据：输入数据：N=10，M=4，K=27，3，4，8，2，6，5，7，4，8v输出答案：输出答案：36v7，3，4，8，2，6，5，7，4，8例三例三最优序列最优序列分析分析 动态规划 线段树？怎么办？“分”超时无从入手O(2MN)！O(21001000)例三例三最优序列最优序列“分分”繁为简繁为简v动态规划之所以不可行，原因在于动态规划之所以不可行，原因在于

4、题目题目中中K和和M的范围太大了！的范围太大了！v利用利用“分分”的思想，我们尝试限制的思想，我们尝试限制K，令，令K=1，也就是对于长度为也就是对于长度为M的子串，最多只选一个的子串，最多只选一个元素作为原题的一个子问题：元素作为原题的一个子问题：例三例三最优序列最优序列子问题子问题v给定一个长度为给定一个长度为N的正整数序列。的正整数序列。v求一个子序列，使得原序列中任意长度为求一个子序列，使得原序列中任意长度为M的子串中被选出的元素不超过的子串中被选出的元素不超过1个。个。v要求选出的元素之和最大。要求选出的元素之和最大。v数据范围：数据范围：1N10001M100例三例三最优序列最优序

5、列“分分”繁为简繁为简v对于这个子问题，由于对于这个子问题，由于K做了限制，我们可做了限制，我们可以用动态规划来解决这个问题。以用动态规划来解决这个问题。v设设dpi表示前表示前i个元素，在满足题意的前提下选出的最大和个元素，在满足题意的前提下选出的最大和 dpi=max(dpi-1,dpi-M+valuei)iM dpi=max(dpi-1,valuei)0iM dp0=0例三例三最优序列最优序列进一步分析进一步分析 子问题子问题原问题原问题是否可以通过求解是否可以通过求解K次的子问题从次的子问题从而解决原题呢而解决原题呢?1K例三例三最优序列最优序列进一步分析进一步分析v命题命题原问题的解

6、集等价于由原问题的解集等价于由K K组互不相交的子问题的解组互不相交的子问题的解组成的解集。组成的解集。v引理一引理一原问题的任意一组解都可以由原问题的任意一组解都可以由K K组不相交的子问题组不相交的子问题的解组成。的解组成。v引理二引理二任意任意K K组不相交的子问题的解的并均为原问题的解。组不相交的子问题的解的并均为原问题的解。v引理一引理一原问题的任意一组解都可以由原问题的任意一组解都可以由K组不相交的组不相交的子问题的解组成。子问题的解组成。v证明证明对于原问题的任意一解对于原问题的任意一解P=a1,a2,a3at，a1a2a3at。设。设sumi表示该解在区间表示该解在区间1,i内

7、取出的元素个数，则根据题意满足不内取出的元素个数，则根据题意满足不等式：等式：sumi-sumi-MK以下，我们给出一种构造法使之能产生一组以下，我们给出一种构造法使之能产生一组与该解等价的与该解等价的K个子问题的解。个子问题的解。设设K个子问题的解分别为个子问题的解分别为P0,P1,P2Pk-1，令令Pi=aj|ji(mod K)sumi-sumi-MKai-ai-kMP0,P1,P2Pk-1均为合法的子问题的解均为合法的子问题的解又因为又因为P0P1P2Pk-1=P，因此我们成，因此我们成功地构造出了子问题的解。功地构造出了子问题的解。v引理二引理二任意任意K组不相交的子问题的解的并均为原

8、问组不相交的子问题的解的并均为原问题的解。题的解。v证明证明设设K个子问题的不相交的解分别为个子问题的不相交的解分别为P0,P1,P2Pk-1，Pi=ai1,ai2,ai3ail，ai1ai2ai3ail对于任意长度为对于任意长度为M的区间，的区间，Pi至多只有一至多只有一个元素在其内部个元素在其内部设设P=P0P1P2Pk-1，则对于任意长度为则对于任意长度为M的区间，的区间，P在其内部选出在其内部选出的元素个数不超过的元素个数不超过K个个任意任意K组互不相交的子问题的解的并都是组互不相交的子问题的解的并都是原问题的合法解。原问题的合法解。引理一与引理二分别证明了命题的充分性和引理一与引理二

9、分别证明了命题的充分性和必要性，因此该命题成立必要性，因此该命题成立例三例三最优序列最优序列进一步分析进一步分析v题目中存在着一个潜条件，即：题目中存在着一个潜条件，即：每个元素只能被选一次每个元素只能被选一次v若直接套用若直接套用K次动态规划来求解，有可能导次动态规划来求解，有可能导致某个元素被取多次，无法满足题目中的这致某个元素被取多次，无法满足题目中的这个条件。个条件。例三例三最优序列最优序列进一步分析进一步分析vN=10，M=4，K=2 3 3 3 3v动态规划：动态规划：12 v贪心：贪心：9标准答案：标准答案：101111111133并并 1 3 1 3 1并并 1 3 1 1 3

10、 1v考虑动态规划与贪心之所以不能得到正确解，考虑动态规划与贪心之所以不能得到正确解，其关键原因在于其关键原因在于题目中存在着一个元素题目中存在着一个元素只能被取一次的限制，而对于这种限制各点只能被取一次的限制，而对于这种限制各点被选取次数的题目，我们通常使用网络流来被选取次数的题目，我们通常使用网络流来解决，那么这道题是否也能通过转化图论模解决，那么这道题是否也能通过转化图论模型来使用网络流解决呢？答案是肯定的。型来使用网络流解决呢？答案是肯定的。例三例三最优序列最优序列整体分析整体分析例三例三最优序列最优序列整体分析整体分析v构造带权网络构造带权网络G=(V,A,C)v序列中的每个元素序列

11、中的每个元素i用顶点用顶点i与与i表示，表示，ii连边，容连边，容量为量为1，费用为该元素的数值，费用为该元素的数值valuei，图中包含源，图中包含源S与汇与汇T。v所有点所有点i向点向点(i+1)连边，容量为连边，容量为+，费用为，费用为0v源源S向所有点向所有点i各连一条边，容量为各连一条边，容量为+，费用为，费用为0v所有点所有点i向汇向汇T各连一条边，容量为各连一条边，容量为+，费用为，费用为0v所有点所有点i向点向点(i+M)连边，容量为连边，容量为+，费用为，费用为0321n123nTS容量容量=1费用费用=valuei容量容量=+费用费用=0例三例三最优序列最优序列整体分析整体

12、分析v构图完成之后，网络中的每个单位流量表示构图完成之后，网络中的每个单位流量表示一个子问题的解，因此，我们只需要在网络一个子问题的解，因此，我们只需要在网络中寻找中寻找K次最大费用增广路即可得到答案。次最大费用增广路即可得到答案。v由于这张图的边数与顶点数同阶，若使用由于这张图的边数与顶点数同阶，若使用SPFA算法求增广轨，则期望时间复杂度仅为算法求增广轨，则期望时间复杂度仅为O(KN)，是个十分优秀的算法。，是个十分优秀的算法。总结总结分分合合对立对立统一统一辨证关系分中有合，合中有分分中有合，合中有分转化“分分”的思想帮助我们迅速地切入问题核心，的思想帮助我们迅速地切入问题核心，但若过分

13、细化则会使问题太过凌乱，失去求但若过分细化则会使问题太过凌乱，失去求解的方向；而解的方向；而“合合”的思想则以线串珠，使的思想则以线串珠，使各种纷杂无序的问题具有了整体性。各种纷杂无序的问题具有了整体性。善于归纳总结善于归纳总结勇于创新勇于创新谢 谢v总结：总结：“分分”与与“合合”虽然对立，却没有明显的分界。虽然对立，却没有明显的分界。一道问题若使用一道问题若使用“分分”的方法，则必然有的方法，则必然有“合合”的操作，的操作，正所谓正所谓“分中有合，合中有分分中有合，合中有分”，这两者相互对立，各，这两者相互对立，各有优势，却又相互补充，有优势，却又相互补充，“分分”的思想帮助我们迅速地的思

14、想帮助我们迅速地切入问题核心，但若过分细化则会使问题太过凌乱，失切入问题核心，但若过分细化则会使问题太过凌乱，失去求解的方向；而去求解的方向；而“合合”的思想则以线串珠，使各种纷的思想则以线串珠，使各种纷杂无序的问题具有了整体性，这正体现了两者之间的辨杂无序的问题具有了整体性，这正体现了两者之间的辨证关系。证关系。v运用运用“分分”与与“合合”的思想，对于不同的题目需要不同的思想，对于不同的题目需要不同的分析，其精髓就在于的分析，其精髓就在于“转化转化”。无论是。无论是“分分”还是还是“合合”都是朝着将问题转化为更加便于思考的方向前进，都是朝着将问题转化为更加便于思考的方向前进，而在这路途中，

15、又需要我们善于归纳总结。只有将已有而在这路途中，又需要我们善于归纳总结。只有将已有的知识与的知识与“分合分合”思想有机地结合起来，同时勇于创新，思想有机地结合起来，同时勇于创新，不断积累经验，我们才能从千变万化的题目中找寻出本不断积累经验，我们才能从千变万化的题目中找寻出本质，从而更快更有效地解决实际问题。质，从而更快更有效地解决实际问题。整体整体部分部分转化目标转化目标动态规划动态规划贪心贪心小结小结线段树无法解决该题的原因线段树无法解决该题的原因v因为原问题是要求对于任意长度为因为原问题是要求对于任意长度为M的区间，的区间，都限制了取数不超过都限制了取数不超过K个。而这些区间有互个。而这些

16、区间有互相有交，这使得线段树很难准确的表示一个相有交，这使得线段树很难准确的表示一个状态并进行处理。状态并进行处理。v更重要的是，线段树只是一个用来提升算法更重要的是，线段树只是一个用来提升算法效率的辅助工具，若要使用线段树，则必须效率的辅助工具，若要使用线段树，则必须先提出一个可行的算法。但对于这题我们很先提出一个可行的算法。但对于这题我们很难想出一个可以使用线段树的算法。难想出一个可以使用线段树的算法。动态规划的解法动态规划的解法v将连续将连续M位的被选状态位的被选状态(0,1)压缩成压缩成M位二进制数表位二进制数表示示,DPi,j表示表示1,i区间区间,最后最后M位状态为位状态为j时的最优时的最优解解,由于满足无后效性和最优子结构性质由于满足无后效性和最优子结构性质,可以使用可以使用动态规划解决动态规划解决,转移方程如下转移方程如下:)valuei1and()2/,1,2/2,1max(,1jjidpjidpjidpm