浅析信息学中分与合.ppt
浅析信息学中的“分”与“合”福建省福州第三中学福建省福州第三中学杨沐杨沐引言引言v分v“分分”的思想是将的思想是将一个难以直接解决一个难以直接解决的大问题，转化成的大问题，转化成一些规模较小或限一些规模较小或限制某些条件的子问制某些条件的子问题来思考，以求将题来思考，以求将问题解决。问题解决。v合v“合合”的思想与的思想与“分分”相对，是将一些零相对，是将一些零散的小问题的解决合散的小问题的解决合并成一个大问题，从并成一个大问题，从而取得整个问题的解而取得整个问题的解决。决。引言引言v例一例一牛奶模版牛奶模版v例二例二树的重建树的重建v例三例三最优序列最优序列二分二分化归化归v运用运用“分分”与与“合合”思想思想方法方法解题的精髓在解题的精髓在于通过在于通过在“分分”与与“合合”之间的转化之间的转化，找出找出解决问题的关键，从而解决问题。解决问题的关键，从而解决问题。“分治法分治法”是是运用运用“分分”与与“合合”思想方法解题的重思想方法解题的重要应用，此外，要应用，此外，“分分”与与“合合”的思想方法的思想方法还有更多、更广泛的应用。还有更多、更广泛的应用。N,K限制下最优化问题限制下最优化问题N,K,Len限制下存在性问题限制下存在性问题规模为规模为n的问题的问题规模为规模为n-1的问题的问题例三例三最优序列最优序列v给定一个长度为给定一个长度为N的正整数序列。的正整数序列。v求一个子序列，使得原序列中任意长度为求一个子序列，使得原序列中任意长度为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动态规划之所以不可行，原因在于动态规划之所以不可行，原因在于题目题目中中K和和M的范围太大了！的范围太大了！v利用利用“分分”的思想，我们尝试限制的思想，我们尝试限制K，令，令K=1，也就是对于长度为，也就是对于长度为M的子串，最多只选一的子串，最多只选一个元素作为原题的一个子问题：个元素作为原题的一个子问题：例三例三最优序列最优序列子问题子问题v给定一个长度为给定一个长度为N的正整数序列。的正整数序列。v求一个子序列，使得原序列中任意长度为求一个子序列，使得原序列中任意长度为M的子串中被选出的元素不超过的子串中被选出的元素不超过1个。个。v要求选出的元素之和最大。要求选出的元素之和最大。v数据范围：数据范围：1N10001M100例三例三最优序列最优序列“分分”繁为繁为简简v对于这个子问题，由于对于这个子问题，由于K做了限制，我们可做了限制，我们可以用动态规划来解决这个问题。以用动态规划来解决这个问题。v设设dpi表示前表示前i个元素，在满足题意的前提下选出的最大和个元素，在满足题意的前提下选出的最大和 dpi=max(dpi-1,dpi-M+valuei)iM dpi=max(dpi-1,valuei)0iM dp0=0例三例三最优序列最优序列进一步分析进一步分析 子问题子问题原问题原问题是否可以通过求解是否可以通过求解K次的子问题从而次的子问题从而解决原题呢解决原题呢?1K例三例三最优序列最优序列进一步分析进一步分析v命题命题原问题的解集等价于由原问题的解集等价于由K K组互不相交的子问题的解组组互不相交的子问题的解组成的解集。成的解集。v引理一引理一原问题的任意一组解都可以由原问题的任意一组解都可以由K K组不相交的子问题的组不相交的子问题的解组成。解组成。v引理二引理二任意任意K K组不相交的子问题的解的并均为原问题的解。组不相交的子问题的解的并均为原问题的解。例三例三最优序列最优序列进一步分析进一步分析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 1v考虑动态规划与贪心之所以不能得到正确解，考虑动态规划与贪心之所以不能得到正确解，其关键原因在于其关键原因在于题目中存在着一个元素题目中存在着一个元素只能被取一次的限制，而对于这种限制各点只能被取一次的限制，而对于这种限制各点被选取次数的题目，我们通常使用网络流来被选取次数的题目，我们通常使用网络流来解决，那么这道题是否也能通过转化图论模解决，那么这道题是否也能通过转化图论模型来使用网络流解决呢？答案是肯定的。型来使用网络流解决呢？答案是肯定的。例三例三最优序列最优序列整体分析整体分析例三例三最优序列最优序列整体分析整体分析v构造带权网络构造带权网络G=(V,A,C)v序列中的每个元素序列中的每个元素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例三例三最优序列最优序列整体分析整体分析v构图完成之后，网络中的每个单位流量表示构图完成之后，网络中的每个单位流量表示一个子问题的解，因此，我们只需要在网络一个子问题的解，因此，我们只需要在网络中寻找中寻找K次最大费用增广路即可得到答案。次最大费用增广路即可得到答案。v由于这张图的边数与顶点数同阶，若使用由于这张图的边数与顶点数同阶，若使用SPFA算法求增广轨，则期望时间复杂度仅为算法求增广轨，则期望时间复杂度仅为O(KN)，是个十分优秀的算法。，是个十分优秀的算法。总结总结分分合合对立对立统一统一辨证关系分中有合，合中有分分中有合，合中有分转化“分分”的思想帮助我们迅速地切入问题核心，的思想帮助我们迅速地切入问题核心，但若过分细化则会使问题太过凌乱，失去求但若过分细化则会使问题太过凌乱，失去求解的方向；而解的方向；而“合合”的思想则以线串珠，使的思想则以线串珠，使各种纷杂无序的问题具有了整体性。各种纷杂无序的问题具有了整体性。善于归纳总结善于归纳总结勇于创新勇于创新谢 谢
