算法合集之《浅析信息学中的“分”与“合”》.ppt

浅析信息学中的 分 与 合 福建省福州第三中学杨沐 引言 分 分 的思想是将一个难以直接解决的大问题 转化成一些规模较小或限制某些条件的子问题来思考 以求将问题解决 合 合 的思想与 分 相对 是将一些零散的小问题的解决合并成一个大问题 从而取得整个问题的解决 话说天下大势 合久必分 分久必合 引言 例一 牛奶模版 例二 树的重建 例三 最优序列 二分化归 运用 分 与 合 思想方法解题的精髓在于通过在 分 与 合 之间的转化 找出解决问题的关键 从而解决问题 分治法 是运用 分 与 合 思想方法解题的重要应用 此外 分 与 合 的思想方法还有更多 更广泛的应用 N K限制下最优化问题 N K Len限制下存在性问题 规模为n的问题 规模为n 1的问题 例三 最优序列 给定一个长度为N的正整数序列 求一个子序列 使得原序列中任意长度为M的子串中被选出的元素不超过K个 要求选出的元素之和最大 数据范围 1 N 10001 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 10001 M 100 例三 最优序列 分 繁为简 对于这个子问题 由于K做了限制 我们可以用动态规划来解决这个问题 设dp i 表示前i个元素 在满足题意的前提下选出的最大和dp i max dp i 1 dp i M value i i Mdp i max dp i 1 value i 0 i Mdp 0 0 例三 最优序列 进一步分析 子问题 原问题 是否可以通过求解K次的子问题从而解决原题呢 1 K 例三 最优序列 进一步分析 命题原问题的解集等价于由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 3333动态规划 12贪心 9 标准答案 10 1 1 1 1 1 1 1 1 3 3 并13131 并131131 考虑动态规划与贪心之所以不能得到正确解 其关键原因在于 题目中存在着一个元素只能被取一次的限制 而对于这种限制各点被选取次数的题目 我们通常使用网络流来解决 那么这道题是否也能通过转化图论模型来使用网络流解决呢 答案是肯定的 例三 最优序列 整体分析 例三 最优序列 整体分析 构造带权网络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 连边 容量为 费用为0 3 2 1 n 1 2 3 n T S 容量 1费用 value i 容量 费用 0 例三 最优序列 整体分析 构图完成之后 网络中的每个单位流量表示一个子问题的解 因此 我们只需要在网络中寻找K次最大费用增广路即可得到答案 由于这张图的边数与顶点数同阶 若使用SPFA算法求增广轨 则期望时间复杂度仅为O KN 是个十分优秀的算法 总结 分 合 对立 统一 辨证关系 分中有合 合中有分 转化 分 的思想帮助我们迅速地切入问题核心 但若过分细化则会使问题太过凌乱 失去求解的方向 而 合 的思想则以线串珠 使各种纷杂无序的问题具有了整体性 善于归纳总结 勇于创新 谢谢 总结 分 与 合 虽然对立 却没有明显的分界 一道问题若使用 分 的方法 则必然有 合 的操作 正所谓 分中有合 合中有分 这两者相互对立 各有优势 却又相互补充 分 的思想帮助我们迅速地切入问题核心 但若过分细化则会使问题太过凌乱 失去求解的方向 而 合 的思想则以线串珠 使各种纷杂无序的问题具有了整体性 这正体现了两者之间的辨证关系 运用 分 与 合 的思想 对于不同的题目需要不同的分析 其精髓就在于 转化 无论是 分 还是 合 都是朝着将问题转化为更加便于思考的方向前进 而在这路途中 又需要我们善于归纳总结 只有将已有的知识与 分合 思想有机地结合起来 同时勇于创新 不断积累经验 我们才能从千变万化的题目中找寻出本质 从而更快更有效地解决实际问题 整体 部分 网络流 转化目标 动态规划 贪心 小结 线段树无法解决该题的原因 因为原问题是要求对于任意长度为M的区间 都限制了取数不超过K个 而这些区间有互相有交 这使得线段树很难准确的表示一个状态并进行处理 更重要的是 线段树只是一个用来提升算法效率的辅助工具 若