浅析信息学中的分与合

浅析信息学中的“分”与“合”福建省福州第三中学杨沐引言分“分”的思想是将一个难以直接解决的大问题，转化成一些规模较小或限制某些条件的子问题来思考，以求将问题解决。合“合”的思想与“分”相对，是将一些零散的小问题的解决合并成一个大问题，从而取得整个问题的解决。话说天下大势，合久必分，分久必合引言[例一]牛奶模版[例二]树的重建[例三]最优序列 二分 化归运用“分”与“合”思想方法解题的精髓在于通过在“分”与“合”之间的转化，找出解决问题的关键，从而解决问题。“分治法”是运用“分”与“合”思想方法解题的重要应用，此外，“分”与“合”的思想方法还有更多、更广泛的应用。N,K限制下最优化问题→N,K,Len限制下存在性问题规模为n的问题→规模为n-1的问题[例三]最优序列给定一个长度为N的正整数序列。求一个子序列，使得原序列中任意长度为M的子串中被选出的元素不超过K个。要求选出的元素之和最大。数据范围：

1≤N≤1000 1≤K，M≤100[例三]最优序列输入数据：

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(2100×1000)[例三]最优序列——“分”繁为简动态规划之所以不可行，原因在于——题目中K和M的范围太大了！利用“分”的思想，我们尝试限制K，令K=1，也就是对于长度为M的子串，最多只选一个元素作为原题的一个子问题：[例三]最优序列——子问题给定一个长度为N的正整数序列。求一个子序列，使得原序列中任意长度为M的子串中被选出的元素不超过1个。要求选出的元素之和最大。数据范围：

1≤N≤1000 1≤M≤100[例三]最优序列——“分”繁为简对于这个子问题，由于K做了限制，我们可以用动态规划来解决这个问题。设dp[i]表示前i个元素，在满足题意的前提下选出的最大和

dp[i]=max(dp[i-1],dp[i-M]+value[i])i≥M

dp[i]=max(dp[i-1],value[i])0<i<Mdp[0]=0[例三]最优序列——进一步分析子问题原问题是否可以通过求解K次的子问题从而解决原题呢?1K[例三]最优序列——进一步分析命题

原问题的解集等价于由K组互不相交的子问题的解组成的解集。引理一 原问题的任意一组解都可以由K组不相交的子问题的解组成。引理二 任意K组不相交的子问题的解的并均为原问题的解。引理一 原问题的任意一组解都可以由K组不相交的子问题的解组成。证明 对于原问题的任意一解P={a1,a2,a3…at}，a1<a2<a3…<at。设sum[i]表示该解在区间[1,i]内取出的元素个数，则根据题意满足不等式：

sum[i]-sum[i-M]≤K 以下，我们给出一种构造法使之能产生一组与该解等价的K个子问题的解。

设K个子问题的解分别为P0,P1,P2…Pk-1， 令Pi={aj|j≡i(modK)} ∵sum[i]-sum[i-M]≤K ∴ai-ai-k≥M ∴P0,P1,P2…Pk-1均为合法的子问题的解 又因为P0∪P1∪P2…∪Pk-1=P，因此我们成功地构造出了子问题的解。

引理二 任意K组不相交的子问题的解的并均为原问题的解。证明 设K个子问题的不相交的解分别为P0,P1,P2…Pk-1

，

Pi={ai1,ai2,ai3…ail}，ai1<ai2<ai3…<ail ∵对于任意长度为M的区间，Pi至多只有一个元素在其内部 设P=P0∪P1∪P2…∪Pk-1， 则对于任意长度为M的区间，P在其内部选出的元素个数不超过K个 ∴任意K组互不相交的子问题的解的并都是原问题的合法解。 引理一与引理二分别证明了命题的充分性和必要性，因此该命题成立[例三]最优序列——进一步分析题目中存在着一个潜条件，即： 每个元素只能被选一次若直接套用K次动态规划来求解，有可能导致某个元素被取多次，无法满足题目中的这个条件。[例三]最优序列——进一步分析N=10，M=4，K=2 { } 3 3 3 3动态规划：12贪心：9标准答案：101111111133并1 3 1 31并1 3 11 31考虑动态规划与贪心之所以不能得到正确解，其关键原因在于——题目中存在着一个元素只能被取一次的限制，而对于这种限制各点被选取次数的题目，我们通常使用网络流来解决，那么这道题是否也能通过转化图论模型来使用网络流解决呢？答案是肯定的。[例三]最优序列——整体分析[例三]最优序列——整体分析构造带权网络G=(V,A,C) 序列中的每个元素i用顶点i与i’表示，i→i’连边，容量为1，费用为该元素的数值value[i]，图中包含源S与汇T。所有点i向点(i+1)连边，容量为+∞，费用为0源S向所有点i各连一条边，容量为+∞，费用为0所有点i’向汇T各连一条边，容量为+∞，费用为0所有点i’向点(i+M)连边，容量为+∞，费用为03’2’1’……n’123nTS……容量=1费用=value[i]容量=+∞费用=0[例三]最优序列——整体分析构图完成之后，网络中的每个单位流量表示一个子问题的解，因此，我们只需要在网络中寻找K次最大费用增广路即可得到答案。由于这张图的边数与顶点数同阶，若使用SPFA算法求增广轨，则期望时间复杂度仅为O(KN)，是个十分优秀的算法。

总结分合对立统一辨证关系分中有合，合中有分转化“分”的思想帮助我们迅速地切入问题核心，但若过分细化则会使问题太过凌乱，失去求解的方向；而“合”的思想则以线串珠，使各种纷杂无序的问题具有了整体性。善于归纳总结勇于创新谢谢总结：“分”与“合”虽然对立，却没有明显的分界。一道问题若使用“分”的方法，则必然有“合”的操作，正所谓“分中有合，合中有分”，这两者相互对立，各有优势，却又相互补充，“分”的思想帮助我们迅速地切入问题核心，但若过分细化则会使问题太过凌乱，失去求解的方向；而“合”的思想则以线串珠，使各种纷杂无序的问题具有了整体性，这正体现了两者之间的辨证关系。运用“分”与“合”的思想，对于不同的题目需要不同的分析，其精髓就在于“转化”。无论是“分”还是“合”都是朝着将问题转化为更加便于思考的方向前进，而在这路途中，又需要我们善于归纳总结。只有将已有的知识与“分合”思想有机地结合起来，同时勇于创新，不断积累经验，我们才能从千变万化的题目中找寻出本质，从而更快更有效地解决实际问题。整体部分网络流！转化目标动态规划贪心小结线段树无法解决该题的原因因为原问题是要求对于任意长度为M的区间，都限制了取数不超过K个。而这些区间有互相有交，这使得线段树很难准确的表示一个状态并进行处理。更重要的是，线段树只是