文档教程知识库【免费下载链接】cp-algorithmsAlgorithm and data structure articles for https://cp-algorithms.com (based on http://e-maxx.ru)项目地址https://gitcode.com/GitHub_Trending/cp/cp-algorithms点击查看免费下载分治 DPDivide 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$ 内部采用递归策略先计算中点状态 $opt(i, n / 2)$由单调性左半部分所有状态的 $opt$ 都 $\leq opt(i, n / 2)$右半部分都 $\geq opt(i, n / 2)$于是递归计算 $opt(i, n / 4)$ 时只需在 $[optl, opt(i, n/2)]$ 内枚举计算 $opt(i, 3n / 4)$ 时只需在 $[opt(i, n/2), optr]$ 内枚举递归地维护每个子区间对应的 $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; vectorlong 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; pairlong 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]; }模板逐行拆解行 5C(i, j)是代价函数题目不同实现不同要求 $O(1)$ 求值且满足四边形不等式。行 8-9best以pair记录(代价, 切分点)min比较时先比代价、再比切分点代价相同取更小的 $k$。行 11mid是当前区间的中点状态下标。分治策略总是先确定中点的最优切分点。行 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-28solve初始化第一行dp_before[i] C(0, i)即 $i0$ 层只有一段时直接取整段区间代价随后对 $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$ 的最后一次出现位置减去第一次出现位置之和。测试里使用mapint,int last在线性扫描中累加(l - last[x])验证了模板对非平凡代价函数的适用性同时brute_force()提供了逐层、逐状态、逐 $k$ 的朴素三重循环版本作为正确性基准。测试脚本如何验证模板仓库的 test/extract_snippets.py 会扫描src/下所有.md用正则^\s*\{.cpp\sfile(\S)\}$匹配代码块并导出为同名.h文件test/test.sh 随后用g -stdc17 -fsanitizeundefined编译所有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最容易翻车的三个点证明opt的单调性是最大难点。绝不能默认所有代价函数都满足单调性。一个充分条件是代价函数满足四边形不等式 $$ C(a, c) C(b, d) \leq C(a, d) C(b, c) \quad (\text{对所有 } a \leq b \leq c \leq d) $$ 许多经典问题的代价如区间内每个值的首末位置差之和、区间内不同元素个数等都可通过排序、交换论证验证该不等式。证明不成立时套用模板会得到错误答案。注意与 Knuth 优化、凸包技巧的辨析。分治 DP 与仓库中的另一篇 Knuth 优化 关系密切两者都依赖最优切分点opt的单调性但递推结构不同——Knuth 优化针对区间 DP 形如 $dp(i,j)\min_{k}{dp(i,k)dp(k1,j)C(i,j)}$ 的递推把 $O(n^3)$ 降到 $O(n^2)$分治 DP 针对上述分层递推把 $O(mn^2)$ 降到 $O(mn\log n)$。此外很多分治 DP 题目也可以用凸包技巧Convex Hull Trick求解反之亦然——两个工具都掌握解题时才能灵活切换。小心 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 RestaurantsCodeForces 321E - Ciel and Gondolas注意 I/OCodeForces 673E - Levels And RegionsCodeForces 1527E - Partition Game即本仓库测试所用的题CodeForces 834D - The BakeryCodeForces 868F - Yet Another Minimization ProblemCodechef CHEFAORCodeForces Gym 103536A - GUARDS本文档原理的精确出处题Hackerrank IOI 2014 Practice - Guardians of the LunaticsHackerrank World Codesprint 5 - MiningKattis - MoneyACM ICPC World Finals 2017SPOJ ADAMOLD、LARMY、NKLEAVESTimus 1167 - Bicolored HorsesUSACO - Circular BarnUVA 12524 - Arranging Heaps、UVA 12594 - Naming Babies延伸阅读Knuth 优化Knuths Optimization另一种基于opt单调性的 DP 加速与本文递推结构互补凸包技巧Convex Hull Trick常见替代方案某些题目两者皆可解仓库动态规划目录 src/dynamic_programming/ 下还有intro-to-dp、knapsack、longest_increasing_subsequence等文章可系统性补齐 DP 基础。赞分享文档教程知识库【免费下载链接】cp-algorithmsAlgorithm and data structure articles for https://cp-algorithms.com (based on http://e-maxx.ru)项目地址https://gitcode.com/GitHub_Trending/cp/cp-algorithms点击查看免费下载相关推荐cp-algorithms 凸包优化与李超线段树从 DP 加速到 O(n log n) 实战指南cp algorithms 凸包优化与李超线段树从 DP 加速到 O n log n 实战指南 导读 本文讲解 cp algorithms 仓库 src/g文档教程知识库cp-algorithms 的 Knuth 优化Knuth–Yao 加速详解区间 DP 从 O(n³) 到 O(n²) 的决策单调性优化cp algorithms 的 Knuth 优化Knuth–Yao 加速详解区间 DP 从 O n³ 到 O n² 的决策单调性优化 本篇技术指南以 cp文档教程知识库5分钟掌握终极跨平台文件传输用croc告别数据同步困境5分钟掌握终极跨平台文件传输用croc告别数据同步困境 还在为设备间的文件传输而烦恼吗U盘容量不足、邮件附件限制、云盘上传龟速、局域网配置复杂……这些困扰开CLI通信密码学上一篇Harper内存使用分析识别优化机会的工具与方法下一篇solar_merge_test_3配置详解从config.json到mergekit_moe_config.yml创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考