企业官网建设流程全解析

• 文档
• 教程
• 知识库

分治 DP（Divide and Conquer DP）是竞赛动态规划中最经典的递推加速技巧之一，专门处理形如 $dp(i,j)=\min_{k}{dp(i-1,k-1)+C(k,j)}$ 的分层递推。本文以 cp-algorithms 仓库中 src/dynamic_programming/divide-and-conquer-dp.md 为骨架，结合仓库内配套测试 test/test_divide_and_conquer_dp.cpp 与代码提取脚本 test/extract_snippets.py，完整讲解前置条件、单调性原理、分治算法流程、复杂度证明、通用 C++ 模板与易错点，并给出可直接运行的练习清单。读完你就能独立证明opt的单调性、套用模板把类似递推从 $O(mn^2)$ 优化到 $O(mn\log n)$。

适用场景：什么样的 DP 递推可以套用分治优化

分治 DP 优化针对的是如下形式的递推：

$$ dp(i, j) = \min_{0 \leq k \leq j} { dp(i - 1, k - 1) + C(k, j) } $$

其中 $C(k, j)$ 是代价函数，且当 $j < 0$ 时规定 $dp(i, j) = 0$。设 $0 \leq i < m$、$0 \leq j < n$，并假设单次求值 $C$ 的时间是 $O(1)$。那么直接按定义递推的复杂度是 $O(m n^2)$：状态数共 $m \times n$ 个，每个状态需要尝试 $n$ 个转移点 $k$。

这类递推的典型语义是"把 $n$ 个元素切分成 $m$ 段的最小代价"：$dp(i, j)$ 表示前 $j$ 个元素分成 $i$ 段的最优代价，$C(k, j)$ 表示第 $i$ 段取 $[k, j]$ 这一段区间时的代价。仓库测试 test/test_divide_and_conquer_dp.cpp 中的brute_force()就是这种朴素 $O(m n^2)$ 写法，作为分治版本正确性的对拍基准。

关键定义：最优切分点 opt

记 $opt(i, j)$ 为使上述表达式取得最小值的 $k$，即"最优切分点"。如果代价函数满足四边形不等式（quadrangle inequality），可以证明对所有 $i, j$ 有：

$$ opt(i, j) \leq opt(i, j + 1) $$

这就是著名的单调性条件（monotonicity condition）：固定层 $i$ 时，最优切分点随 $j$ 的增大而单调不减。这一结论是整个优化成立的理论根基，也是实现中optl/optr两个搜索边界存在的依据。

单调性如何省时间

单调性的价值在于：已知 $opt(i, j)$ 后，对任意 $j' < j$ 都有 $opt(i, j') \leq opt(i, j)$。也就是说，计算 $opt(i, j')$ 时不必再把 $[0, j']$ 内所有切分点全部试一遍，上界被 $opt(i, j)$ 卡住了——每行需要枚举的切分点总数大幅收窄。

分治思路：按中点递归收缩搜索区间

朴素 DP 每个状态独立扫 $k$，导致总代价 $O(m n^2)$。分治优化在每一行 $i$ 内部采用递归策略：

1. 先计算中点状态 $opt(i, n / 2)$；
2. 由单调性，左半部分所有状态的 $opt$ 都 $\leq opt(i, n / 2)$，右半部分都 $\geq opt(i, n / 2)$；
3. 于是递归计算 $opt(i, n / 4)$ 时只需在 $[optl, opt(i, n/2)]$ 内枚举，计算 $opt(i, 3n / 4)$ 时只需在 $[opt(i, n/2), optr]$ 内枚举；
4. 递归地维护每个子区间对应的 $opt$ 上下界，最终把单行复杂度压到 $O(n \log n)$，整张 DP 表为 $O(m n \log n)$。

这个"先求中点、再递归两侧、每次用中点结果收窄两侧搜索范围"的流程，与二分思想同源，也是它得名"分治 DP"的原因。

复杂度证明

设递归的第 $k$ 层所有 $opt$ 区间的总长度为 $S_k$（代码中记作 $optl$ 与 $optr$）。观察到：第 $k$ 层任意一个长度为 $x$ 的区间被拆成左右两半后，两侧新区间长度之和至多为 $x + 1$；而第 $k$ 层最多执行 $2^k$ 次拆分，因此：

$$ S_{k + 1} \leq S_k + 2^k $$

以 $S_0 = n$ 为初值归纳可得每层满足：

$$ S_k < n + 2^k \in O(n) $$

由于整个递归只有 $O(\log n)$ 层，且每层的工作量都是 $O(n)$，所以单次分治复杂度为 $O(n \log n)$，整张 DP 表的复杂度为 $O(m n \log n)$。

通用 C++ 模板：compute 与 solve

下面的模板与仓库文档中的实现完全一致。compute负责在给定 $opt$ 搜索范围 $[optl, optr]$ 内，计算第 $i$ 行的dp_cur[l..r]；solve逐行调用compute(0, n-1, 0, n-1)得到答案。仓库通过 test/extract_snippets.py 把该代码块导出为divide_and_conquer_dp.h，再由 test/test_divide_and_conquer_dp.cpp 以#include "divide_and_conquer_dp.h"的方式直接编译测试，因此下面代码可直接复制到你的工程中使用。

int m, n; vector<long long> dp_before, dp_cur; long long C(int i, int j); // compute dp_cur[l], ... dp_cur[r] (inclusive) void compute(int l, int r, int optl, int optr) { if (l > r) return; int mid = (l + r) >> 1; pair<long long, int> best = {LLONG_MAX, -1}; for (int k = optl; k <= min(mid, optr); k++) { best = min(best, {(k ? dp_before[k - 1] : 0) + C(k, mid), k}); } dp_cur[mid] = best.first; int opt = best.second; compute(l, mid - 1, optl, opt); compute(mid + 1, r, opt, optr); } long long solve() { dp_before.assign(n,0); dp_cur.assign(n,0); for (int i = 0; i < n; i++) dp_before[i] = C(0, i); for (int i = 1; i < m; i++) { compute(0, n - 1, 0, n - 1); dp_before = dp_cur; } return dp_before[n - 1]; }

模板逐行拆解

• 行 5：C(i, j)是代价函数，题目不同实现不同，要求 $O(1)$ 求值，且满足四边形不等式。
• 行 8-9：best以pair记录(代价, 切分点)，min比较时先比代价、再比切分点，代价相同取更小的 $k$。
• 行 11：mid是当前区间的中点状态下标。分治策略总是先确定中点的最优切分点。
• 行 13-16：在收窄后的范围 $[optl, \min(mid, optr)]$ 内枚举切分点 $k$。注意上界必须是min(mid, optr)，因为切分点 $k$ 不能超过当前状态 $j = mid$ 本身。(k ? dp_before[k - 1] : 0)正是递推式中的 $dp(i-1, k-1)$，当 $k = 0$ 时按约定取 $0$。
• 行 18-21：把中点结果写回dp_cur[mid]，并按其最优切分点opt递归左右两侧：左侧搜索范围上界收窄为opt，右侧搜索范围下界抬高为opt——这就是单调性在实现层面的体现。
• 行 25-28：solve初始化第一行dp_before[i] = C(0, i)，即 $i=0$ 层只有一段时直接取整段区间代价；随后对 $i = 1..m-1$ 每层调用一次compute(0, n-1, 0, n-1)，完成后把dp_cur滚成dp_before，最终答案在dp_before[n - 1]。

两种代价函数实现对比：模板 vs 测试

仓库测试 test/test_divide_and_conquer_dp.cpp 中实现的C(i, j)对应 CF 1527E "Partition Game"：代价定义为区间 $[i, j]$ 内每个不同值 $x$ 的"最后一次出现位置减去第一次出现位置"之和。测试里使用map<int,int> last在线性扫描中累加(l - last[x])，验证了模板对非平凡代价函数的适用性；同时brute_force()提供了逐层、逐状态、逐 $k$ 的朴素三重循环版本作为正确性基准。

测试脚本如何验证模板

仓库的 test/extract_snippets.py 会扫描src/下所有.md，用正则^\s*```\{.cpp\s+file=(\S+)\}$匹配代码块并导出为同名.h文件；test/test.sh 随后用g++ -std=c++17 -fsanitize=undefined编译所有test_*.cpp并逐个运行。test_divide_and_conquer_dp.cpp包含两类用例：

• 手工构造用例：m = 3、数组长度 38，断言solve() == 30；
• 随机对拍：随机生成 $n$、数组值和 $m \in [1, n]$，逐一对solve()与brute_force()的结果做assert相等（100 组、值域 1..5 的小规模数据）。

这意味着模板的正确性在仓库 CI 中持续被验证，你可以放心作为自己解题的起点。

Things to look out for：最容易翻车的三个点

1. 证明opt的单调性是最大难点。绝不能默认所有代价函数都满足单调性。一个充分条件是代价函数满足四边形不等式： $$ C(a, c) + C(b, d) \leq C(a, d) + C(b, c) \quad (\text{对所有 } a \leq b \leq c \leq d) $$ 许多经典问题的代价（如区间内"每个值的首末位置差之和"、"区间内不同元素个数"等）都可通过排序、交换论证验证该不等式。证明不成立时套用模板会得到错误答案。

2. 注意与 Knuth 优化、凸包技巧的辨析。分治 DP 与仓库中的另一篇 Knuth 优化 关系密切：两者都依赖最优切分点opt的单调性，但递推结构不同——Knuth 优化针对区间 DP 形如 $dp(i,j)=\min_{k}{dp(i,k)+dp(k+1,j)+C(i,j)}$ 的递推，把 $O(n^3)$ 降到 $O(n^2)$；分治 DP 针对上述分层递推，把 $O(mn^2)$ 降到 $O(mn\log n)$。此外，很多分治 DP 题目也可以用凸包技巧（Convex Hull Trick）求解，反之亦然——两个工具都掌握，解题时才能灵活切换。

3. 小心 I/O 与边界。典型如 CF 321E "Ciel and Gondolas" 对输入输出敏感；同时留意切分点枚举上界必须取min(mid, optr)，以及k = 0时dp_before[k-1]的下标保护。测试用例中同样注意了j < 0时 $dp = 0$ 的约定。

练习问题清单

以下题目均可在理解本模板后直接上手练习（与仓库文档中的 Practice Problems 一致）：

• AtCoder ARC067 D - Yakiniku Restaurants
• CodeForces 321E - Ciel and Gondolas（注意 I/O）
• CodeForces 673E - Levels And Regions
• CodeForces 1527E - Partition Game（即本仓库测试所用的题）
• CodeForces 834D - The Bakery
• CodeForces 868F - Yet Another Minimization Problem
• Codechef CHEFAOR
• CodeForces Gym 103536A - GUARDS（本文档原理的精确出处题）
• Hackerrank IOI 2014 Practice - Guardians of the Lunatics
• Hackerrank World Codesprint 5 - Mining
• Kattis - Money（ACM ICPC World Finals 2017）
• SPOJ ADAMOLD、LARMY、NKLEAVES
• Timus 1167 - Bicolored Horses
• USACO - Circular Barn
• UVA 12524 - Arranging Heaps、UVA 12594 - Naming Babies

延伸阅读

• Knuth 优化（Knuth's Optimization）：另一种基于opt单调性的 DP 加速，与本文递推结构互补；
• 凸包技巧（Convex Hull Trick）：常见替代方案，某些题目两者皆可解；
• 仓库动态规划目录 src/dynamic_programming/ 下还有intro-to-dp、knapsack、longest_increasing_subsequence等文章，可系统性补齐 DP 基础。

• 文档
• 教程
• 知识库