分治优化 dp

aeifean · 2025-09-15 19:40:51 · 算法·理论

感觉这个套路有点强，所以记录一下。

写的可能有点问题 （轻喷），欢迎各位大佬指出。

写得可能不是很完善，欢迎各位大佬补充。

分治思想就不做介绍了，本文不讨论分治做转移分层的决策单调性。

适用情况

对于转移形如 f(i) = \min\limits_{j < i} (f(j) + w(j, i)) 或者 f(i) = \min\limits_{j < i} (w(j, i)) 的 dp。

如果贡献函数 w 具有可合并性，即 w(l, r) 可以通过 w(l, k) 和 w(k + 1, r), k \in [l, r) 合并得到那么它可能可以使用分治来优化，值得注意的是转移不分层不一定可以优化，一般而言可以将 \mathcal{O}(N ^ 2) 优化到 \mathcal{O}(N m \log N)，\mathcal{O}(m) 是合并贡献的复杂度。

过程

我们考虑设计函数 \text{solve}(l, r) 表示处理区间 [l, r] 的转移：

• 如果 l = r，那么单独处理这一个位置的贡献，然后结束递归。
• 先求出 mid = \lfloor \frac{l + r}{2} \rfloor。
• 递归处理 \text{solve}(l, mid) 和 \text{solve}(mid + 1, r)。
• 然后将 [l, mid] 向 [mid + 1, r] 挨个转移，然后考虑是否继承 [l, mid] 的处理结果。
• 最后回溯到上一层。

过程看起来很简单，但是这个思想带来的优势是非常大的。

首先我们不需要动态的加入元素，也就是说我们可以将处理了的元素所有信息静态维护，不需要管另外一边对已处理元素贡献的影响。

还有 dp 树是可能的 dp 树中深度最小的，这就让一些可能的暴力复杂度正确。

例题

CF 1442 D

题目描述

有 N(1 \le N \le 3000) 个物品组，第 i 个物品组有 t_i(1 \le \sum t_i \le 10 ^ 6) 个元素，第 i 个物品组第 j 个物品的贡献是 a_{i, j}(1 \le a_{i, j} \le 10 ^ 8)，同时满足 \forall j \in [1, t_i - 1], a_{i, j} \le a_{i, j + 1}，现在可以选择 k(1 \le k \le 3000) 个物品，每个物品只能选一次，且选择第 i 组第 j 个物品之前必须将第 i 组 1 到 j - 1 的物品选择完，要求最大化贡献。

思路

一个简单的贪心是我每次肯定是选择拿完一组物品是最优秀的。

因此根据这个贪心，我们可以将物品组分成三类，第一类是拿完了的，第二类是拿了部分，第三类没有拿元素，很显然第二类物品最多只有一组。

因此我们可以枚举第二类物品是哪一组，剩下的组通过零一背包求出最大贡献。

这样子的复杂度是 \mathcal{O}(N ^ 2 k) 的。

怎么优化呢，我们考虑这个算法的瓶颈在哪里，我们每次需要重新求出来 N - 1 个物品的背包，其实是没有必要的。

我们考虑分治，尽可能利用信息。考虑现在处理了区间 [l, r] 的背包，然后直接回溯剩给上一层，对于 l = r 的节点单独跑一个零一背包，这样子我们只需要做总共 \mathcal{O}(N) 次合并两个背包，复杂度降到了 \mathcal{O}(Nk \log N)。

CF 1175 G

题面描述

给定一个数组 a_1​,a_2​,…,a_n​，你需要将其分成 k 个子段（每个元素恰好属于一个子段）。

一个子段 a_l​,a_{l+1}​,…,a_r​ 的权值定义为 (r−l+1)⋅l≤i≤r\max​(a_i​)。一个划分的权值是所有子段权值之和。

请你找到权值最小的划分方案。

思路

设 f(i, k) 表示前 i 个数划分 k 段的最小贡献。

然后考虑分治处理，考虑现在用 [l, mid] 转移 [mid + 1, r]。

我们设 mx_{1, j} = \max\limits_{i = j + 1} ^ {mid} a_i, mx_{2, j} = \max\limits_{i = mid + 1} ^ j a_i。

接下来我们分别考虑 mx_{1, j} \ge mx_{2, i} 和 mx_{1, j} < mx_{2, i} 的情况。

先考虑 mx_{1, j} \ge mx_{2, i} 的情况，f(i, k) = \min(f(j, k - 1) - j mx_{1, j} + i mx_{1, j})我们从大到小枚举 i，从小到大枚举 j，然后依次加入线段就可以了，李超线段树查询一下。

对于 mx_{1, j} < mx_{2, i} 的情况，f(i, k) = \min(f(j, k - 1) - jmx_{2, i}) + imx_{2, i}，同样的将 i 从小到大来，然后 j 从大到小来，同样用李超线段树维护。

总结

分治可以将转移转换为静态的从已有的元素转移给新的元素，而不需要动态插入，在贡献可合并的情况，复杂度是比较优秀的。

练习题

• CEOI 2017 Building Bridges。