浅析信息学中的浅析信息学中的“ “分分” ”与与“ “合合” ”福建省福州第三中学 杨沐引言v分v“分”的思想是将 一个难以直接解 决的大问题，转 化成一些规模较 小或限制某些条 件的子问题来思 考，以求将问题 解决。v合v“合”的思想与“分” 相对，是将一些零 散的小问题的解决 合并成一个大问题 ，从而取得整个问 题的解决。引言v例一牛奶模版v例二树的重建v例三最优序列二分化归v运用“分”与“合”思想方法解题的精髓在于通 过在“分”与“合”之间的转化，找出解决问题 的关键，从而解决问题。 “分治法”是运用“ 分”与“合”思想方法解题的重要应用，此外 ，“分”与“合”的思想方法还有更多、更广泛 的应用。N,K限制下最优化问题N,K,Len限制下存在性问题规模为n的问题规模为n-1的问题例三最优序列v给定一个长度为N的正整数序列。v求一个子序列，使得原序列中任意长度为M 的子串中被选出的元素不超过K个。v要求选出的元素之和最大。v数据范围： 1N1000 1K，M100例三最优序列v输入数据： N=10，M=4，K=2 7，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数据范围： 1N1000 1M100例三最优序列“分”繁为简v对于这个子问题，由于K做了限制，我们可 以用动态规划来解决这个问题。v设dpi表示前i个元素，在满足题意的前提下选出的最大 和dpi=max(dpi-1,dpi-M+valuei) iMdpi=max(dpi-1,valuei) 0iMdp0=0例三最优序列进一步分析 子问题原问 题是否可以通过求解K次的子问题从而 解决原题呢? 1K例三最优序列进一步分析v命题 原问题的解集等价于由K组互不相交的子问题的解 组成的解集。v引理一 原问题的任意一组解都可以由K组不相交的子问题 的解组成。v引理二 任意K组不相交的子问题的解的并均为原问题的解 。v引理一 原问题的任意一组解都可以由K组不相交的 子问题的解组成。v证明 对于原问题的任意一解P=a1,a2,a3at， a1a2a3at。设sumi表示该解在区间 1,i内取出的元素个数，则根据题意满足不 等式： sumi-sumi-MK以下，我们给出一种构造法使之能产生一组 与该解等价的K个子问题的解。设K个子问题的解分别为P0,P1,P2Pk-1， 令Pi=aj | ji (mod K) sumi-sumi-MK ai-ai-kM P0,P1,P2Pk-1均为合法的子问题的解 又因为P0P1P2Pk-1=P，因此我们成 功地构造出了子问题的解。 v引理二 任意K组不相交的子问题的解的并均为原问 题的解。v证明 设K个子问题的不相交的解分别为 P0,P1,P2Pk-1 ， Pi=ai1,ai2,ai3ail，ai1ai2ai3ail 对于任意长度为M的区间，Pi至多只有一 个元素在其内部设P=P0P1P2Pk-1， 则对于任意长度为M的区间，P在其内部选 出的元素个数不超过K个 任意K组互不相交的子问题的解的并都是 原问题的合法解。引理一与引理二分别证明了命题的充分性和 必要性，因此该命题成立例三最优序列进一步分析v题目中存在着一个潜条件，即： 每个元素只能被选一次v若直接套用K次动态规划来求解，有可能导 致某个元素被取多次，无法满足题目中的这 个条件。例三最优序列进一步分析vN=10，M=4，K=2 3 33 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)，是个十分优秀的算法。 总结分合对立统一辨证关系分中有合，合中有分转化“分”的思想帮助我们迅速地切入问题核心， 但若过分细化则会使问题太过凌乱，失去求 解的方向；而“合”的思想则以线串珠，使各 种纷杂无序的问题具有了整体性。善于归纳总结 勇于创新谢 谢v总结：“分”与“合”虽然对立，却没有明显的分界。一 道问题若使用“分”的方法，则必然有“合”的操作，正 所谓“分中有合，合中有分”，这两者相互对立，各有 优势，却又相互补充，“分”的思想帮助我们迅速地切 入问题核心，但若过分细化则会使问题太过凌乱，失 去求解的方向；而“合”的思想则以线串珠，使各种纷 杂无序的问题具有了整体性，这正体现了两者之间的 辨证关系。 v运用“分”与“合”的思想，对于不同的题目需要不同的 分析，其精髓就在于“转化”。无论是“分”还是“合”都 是朝着将问题转化为更加便于思考的方向前进，而在 这路途中，又需要我们善于归纳总结。只有将已有的 知识与“分合”思想有机地结合起来，同时勇于创新， 不断积累经验，我们才能从千变万化的题目中找寻出 本质，从而更快更有效地解决实际问题。整体部分网络流！网络流！转化目标动态规划贪心小结线段树无法解决该题的原因v因为原问题是要求对于任意长度为M的区间 ，都限制了取数不超过K个。而这些区间有 互相有交，这使得线段树很难准确的表示一 个状态并进行处理。v更重要的是，线段树只是一个用来提升算法 效率的辅助工具，若要使用线段树，则必须 先提出一个可行的算法。但对于这题我们很 难想出一个可以使用线段树的算法。动态规划的解法v将连续M位的被选状态(0,1)压缩成M位二进制数 表示,DPi,j表示1,i区间,最后M位状态为j时的最 优解,由于满足无后效性和最优子结构性质,可以 使用动态规划解决,转移方程如下: