做动态规划题最怕的就是转移方程列出来了结果一看复杂度是 O(n^2)数据范围还给你拉满到 10^5。这时候“凸包优化”就是最常用的救命手段之一竞赛圈一般叫它 Convex Hull Trick简称 CHT。先说明一下这里的 dp 是动态规划不是显示接口那个 DP不然方向就跑偏了。CHT 的核心能力其实就一句话遇到形如 dp[i] min(dp[j] 某种一次函数交叉项) 的转移它能把你“枚举所有 j 找最优决策”的 O(n) 过程压缩成 O(log n) 甚至均摊 O(1)。很多看起来完全没法下手的题一旦识别出这种结构直接套模板就能过。这篇文章我就从为什么能用、怎么判断、怎么实现到经典题逐步拆解把 CHT 的坑和经验一次性讲透。适合想突破 DP 优化、刷题遇到瓶颈、或者准备算法竞赛的读者。1. 先弄明白凸包优化到底在优化什么1.1 一类特别常见的 DP 瓶颈很多 DP 题长这样dp[i] 表示处理到第 i 个位置的最优值转移时需要从前面的某个位置 j 转移过来代价是一个关于 i 和 j 都有关的函数 cost(i, j)。标准转移式是dp[i] min { dp[j] cost(i, j) }其中 0 ≤ j i。如果 cost(i, j) 只是一个只跟 i 有关或只跟 j 有关的项那很简单边扫边维护最小值就行。但麻烦的是 cost(i, j) 里经常出现“i 乘以 j”这种交叉项比如 cost(i, j) (S[i] - S[j])^2、cost(i, j) (A[i] - A[j])^2展开之后就会出现 A[i] * B[j] 这种东西。你更新 dp[i] 时j 每取一个值得到的候选值都不一样必须全部扫一遍于是复杂度稳稳地变成 O(n^2)。数据量小无所谓几千个点顶着跑也行。但一旦 n 到 10^5O(n^2) 就是 10^10 次运算什么优化都救不回来。这时候要做的事情就是找到一种数据结构把这一堆 j 组织起来让“找最小值”这一步变得更快。1.2 把决策点看成直线CHT 最精彩的地方是把“决策点 j”这个抽象概念转换成了“一条直线”。怎么转强行把转移方程改写成关于 i 的一次函数形式。假设你的转移式能整理成这种格式dp[i] min_j { k_j * x_i b_j } C[i]其中 k_j 和 b_j 都只跟 j 有关x_i 只跟 i 有关C[i] 也是只跟 i 有关的常数项。对于每一个 jk_j * x b_j 就是一条以 x 为自变量的直线。而 dp[i] 的计算就变成了“在所有直线中求 x x_i 这一点的最小 y 值”。于是问题从“扫所有 j”变成了“维护一堆直线支持插入一条新直线、查询某个 x 处所有直线的最小值”。但这里有个很自然的问题直线可能有很多条逐条比较不还是 O(n) 吗关键来了一堆直线放在一起真正对答案有贡献的只有最外面那一圈也就是下包络线。对求最小值来说它构成一个下凸包对求最大值来说就是上凸包。包络线内部的那些直线在任何 x 处都不可能是最优解可以直接淘汰。维护这个包络线让插入和查询都变得很高效。1.3 什么样的 DP 题能用 CHT判断一道题能不能用 CHT我总结出来一个很实用的检查顺序第一转移式是不是 dp[i] min_j (dp[j] cost(j, i)) 这种形式。第二cost(j, i) 能不能拆成“一个只跟 j 相关的量 × 一个只跟 i 相关的量 其他只跟 j 相关的量 其他只跟 i 相关的量”。第三拆完之后能不能把 j 相关的部分组织成一条直线的斜率和截距。最典型的例子是分段费用类问题。比如把一个序列分成若干连续段每段费用定义为区间和的平方之类展开后就会出现 S[i] * S[j] 的交叉项这就是标准的 CHT 结构。还有一些有决策单调性的题虽然不显式是直线形式但本质相同。CHT 和决策单调性经常被放在一起讨论其实 CHT 有时候更直接因为决策单调性说明最优决策点单调移动而 CHT 直接通过维护凸包把最优决策“算”出来了。2. 两种主流实现先选型再说细节确定能用 CHT 之后下一步是选实现方案。不同题目的单调性条件不一样最优方案也不同。2.1 斜率单调 查询单调单调队列 O(n)最理想的情况是你插入直线的斜率 k_j 随着 j 增大是单调的不管是递增还是递减同时查询点 x_i 随着 i 增大也是单调的。这时候可以用一个双端队列来维护凸包插入和查询都是均摊 O(1)总复杂度 O(n)这是 CHT 里最爽的一种。原理不复杂。队列里维护的是“当前还没被淘汰的直线”并且相邻直线的交点横坐标从左到右是单调递增的。插入新直线时先看队尾两条直线和新直线的交点关系。如果新直线会让队尾那条直线在所有 x 上都永远不可能成为最优解就把队尾弹掉这个判断通常叫 bad 函数或 is_obsolete。查询时因为 x_i 单调递增最优直线在队列里的位置只会向右移动不会回头。所以每次查询前比较队头第一条直线和第二条直线在当前 x 下的值如果第二条更优说明队头已经过时了弹出队头继续比较。整个过程就是一边弹出过时直线一边取下队头作为答案。这里要特别注意我说的“斜率单调”指的是插入顺序。很多题目天然满足比如玩具装箱这种斜率是前缀和相关的单调函数。如果斜率不单调队尾插入的逻辑就直接失效不能用这个方案。2.2 不满足单调性李超线段树兜底如果斜率或者查询点不单调单调队列方案就用不了。比如斜率可能忽大忽小或者查询点并不是随着 i 递增的这时候就要上更通用的工具李超线段树。李超线段树的做法是把每条直线表示成线段树上的一个“永久标记”。每个节点存一条直线插入新直线时在包含整个定义域的根节点出发沿着线段树往下走。走到某个节点如果新直线在这个节点代表的中点处比已有直线更优就交换两者然后继续往新直线可能更优的子区间递归。查询某个 x 时从根一路走到叶子把所有经过节点上存的直线都在 x 处求个值取最小或最大就行。这样插入一条直线是 O(log V)查询一个点是 O(log V)其中 V 是 x 的取值值域。因为完全不依赖斜率和查询点的单调性所以它能处理的情况更多。代价是代码量比单调队列大不少而且如果 x 范围很大通常需要先对 x 做离散化。李超线段树的思路理解起来并不难其实就是“永久化线段树上保存最优直线”的技巧。我个人的建议是把单调队列版式和李超树版式都背熟因为比赛中没时间现场推 bad 函数。2.3 两种方案怎么选这里我直接给一个对照表方便你快速做决策。方案适用条件插入复杂度查询复杂度代码量单调队列斜率单调且查询点单调均摊 O(1)均摊 O(1)少李超线段树无限制任意斜率/查询点O(log V)O(log V)中CDQ 分治斜率/查询点任意离线O(log n)额外O(log n)额外多如果你是比赛选手我的建议很简单先判断题目是否满足双单调满足就直接单调队列不满足直接用李超树别花时间去写 CDQ。3. 实战经典“玩具装箱”从方程到 AC 代码光讲理论没有说服力拿最经典的“玩具装箱”来走一遍完整流程。这道题几乎就是 CHT 的入门必修课理解了它很多同类题都是一层窗户纸。3.1 题目与 DP 方程推导题意大致是有 n 个玩具长度分别是 C[i]需要把它们分成若干连续段。每一段 [j1, i] 装箱的费用是“该段总长度 段内玩具数 - 1 - L”的平方其中 L 是给定的装箱常数。目标是让总费用最小。设前缀和 S[i] C[1] C[2] ... C[i]。那么第 j1 到 i 这一段实际占用的长度为(i - j) (S[i] - S[j]) - 1 (S[i] i) - (S[j] j) - 1令 T[i] S[i] i那么费用变成(T[i] - T[j] - (L 1))^2于是转移方程写出来dp[i] min { dp[j] (T[i] - T[j] - (L 1))^2 }0 ≤ j i这个形式很经典每个候选项是一个完全平方展开后一定会有交叉项。可以用 CHT。3.2 展开成直线形式为了方便记 M L 1。把平方展开(T[i] - T[j] - M)^2 (T[i] - (T[j] M))^2 T[i]^2 - 2 · T[i] · (T[j] M) (T[j] M)^2代入 dp[i] 的转移式dp[i] min_j { dp[j] - 2 · T[i] · (T[j] M) (T[j] M)^2 } T[i]^2现在把里面和 j 有关的部分看成一条直线斜率 k(j) -2 · (T[j] M)截距 b(j) dp[j] (T[j] M)^2查询时自变量 x T[i]于是 dp[i] min_j { k(j) · T[i] b(j) } T[i]^2。这里还需要确认单调性。T[i] 是 C[i] 的前缀和再加 i题目给的 C[i] 是非负的所以 T[i] 严格递增查询点单调。再看斜率 k(j) -2 · (T[j] M)因为 T[j] 递增所以斜率严格递减插入顺序也是单调的。完美满足单调队列方案的条件。3.3 单调队列版完整代码#include bits/stdc.h using namespace std; using ll long long; using i128 __int128_t; struct Line { ll k, b; ll get(ll x) const { return (ll)((i128)k * x b); } }; // 判断直线 b 是否已经失效 // 前提a.k b.k c.k维护的是下凸包 bool bad(const Line a, const Line b, const Line c) { return (i128)(b.b - a.b) * (b.k - c.k) (i128)(c.b - b.b) * (a.k - b.k); } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; ll L; cin n L; L; // 把 L1 作为新常数方便写式子 vectorll T(n 1, 0); for (int i 1; i n; i) { ll c; cin c; T[i] T[i - 1] c 1; // 这里直接维护 S[i] i } vectorll dp(n 1, 0); dequeLine q; auto add_line [](ll k, ll b) { Line nw{k, b}; while (q.size() 2 bad(q[q.size() - 2], q[q.size() - 1], nw)) { q.pop_back(); } q.push_back(nw); }; auto query [](ll x) { while (q.size() 2 q[1].get(x) q[0].get(x)) { q.pop_front(); } return q.front().get(x); }; // j 0 的直线k -2 * (T[0] L)b dp[0] (T[0] L)^2 add_line(-2 * L, L * L); for (int i 1; i n; i) { dp[i] query(T[i]) T[i] * T[i]; ll P T[i] L; add_line(-2 * P, dp[i] P * P); } cout dp[n] \n; return 0; }代码里有一个关键点我维护的 T[i] 其实已经在循环里多加了一个 1也就是直接存 S[i] i这样最后面的公式看起来更干净。你如果习惯用原版前缀和也完全可以只要保证公式对应上。3.4 代码里每一步都在做什么add_line 里的 bad 函数是整个 CHT 的核心。它的几何含义是三条直线 a, b, c 的斜率依次递减时如果直线 a 和 b 的交点比直线 b 和 c 的交点更靠右那么 b 在整个数轴上永远不会成为最下面的那条线直接删掉。如果不删后续查询可能会错误地选到它。公式里的交叉相乘是为了避免浮点除法。直接算交点需要用 double容易出现精度问题。写成整数乘法的形式再用 __int128 防止中间结果溢出这样既快又稳。query 函数里队头两条直线比较如果第二条直线在当前 x 处更小说明队头这条已经沦为过时直线。因为查询点 x 是递增的它以后也不可能翻盘所以放心弹出。这个“以后不可能翻盘”的判断依赖的是查询点的单调性所以用单调队列方案时这一点绝不能破坏。最后注意循环顺序dp[i] 要先查询再插入当前 i 对应的直线。因为决策 j 必须严格小于 i不能自己转移到自己。你先插入再查询就会出现 dp[i] 从自己转移的错误结果这个细节很多人第一次写都会踩。4. 常见问题与排查技巧实录CHT 代码不长但坑特别多。下面这些是我自己写题、看别人代码时反复遇到的坑整理成速查建议。4.1 斜率相等和除零问题怎么处理很多题目虽然一般保证斜率单调但没有说不会出现相同斜率。如果插入新直线时队尾直线斜率相等bad 函数里的交叉相乘公式在数学上其实是从交点公式推导出来的斜率相等时交点可能是无穷大直接套会有问题。处理方式很简单插入之前先判断一下如果新直线的斜率和队尾直线斜率相同那么只保留截距更小的那一条求最小值时。因为斜率一样两条线平行在任何 x 处截距小的永远更优另一条完全没用。同理队头弹出时如果两条线斜率相同也一样处理。我一般会在 add_line 的最前面加一段if (!q.empty() q.back().k nw.k) { if (q.back().b nw.b) return; q.pop_back(); }这样 bad 函数就不会遇到分母为 0 的情况。4.2 什么时候该用 long long / __int128CHT 的插入和查询本质上是在做一次函数求值涉及乘法和加法。如果坐标范围大中间结果很容易爆 int。我的习惯是只要有乘法就先把类型提升到 long long如果数据范围是 10^9 级别或者前缀和平方会到 10^18比较和求值就一定用 __int128。上面的代码里 get 函数使用了 __int128 做乘法但是最终结果强制转换回 long long前提是题目保证答案在 long long 范围内。如果题目答案也会超那你得把 dp 数组、get 返回值、输出函数全部改成 __int128 版本。知道这个边界很重要不要想当然。4.3 单调性判断错了症状和修正最隐蔽的问题不是代码而是“条件判断”。很多人推导完直线形式后直接套单调队列模板结果 WA 到怀疑人生。原因往往是斜率其实是递增的但你用递减的 bad 函数公式去处理或者查询点并不是严格递增的你还在 query 里盲目弹队头。如果你的代码在随机数据下经常错但小数据能过优先检查这三点插入直线时斜率的单调方向是什么bad 函数的方向写反没有。查询点是否真的单调。有的题目查询点是 S[i] 的绝对值可能一开始增后面减根本不是单调的。维护的是上凸包还是下凸包。求最小值用下凸包求最大值要反过来。一个很实用的验证方法把每步队列里的直线打印出来再手动计算一下当前轮次应该选哪个 j。如果实际选出来的 j 和暴力算的不一致看看是不是队头弹早了。下面是一个常见错误排查速查表现象可能原因处理方式答案偏大队头弹出条件错了检查查询 x 是否单调检查取等方向答案随机波动bad 函数几何方向反了画三条直线手算交点验证运行时报错除零插入前处理斜率相等或检查交叉相乘公式用 long long 溢出中间结果超范围乘法改成 __int128小数据对大数据错栈退化 / 重复直线检查相同斜率的合并逻辑4.4 调试利器暴力对拍写 CHT 题我强烈建议你养一个“对拍”的习惯尤其是刚学的时候。因为 CHT 的正确性不是那么直白暴力 dp 虽然慢但正确性显然。你可以写一个 O(n^2) 的暴力版本随机生成小数据把暴力结果和 CHT 结果对比能帮你快速锁定问题。对拍时注意数据范围不要太大n 控制在 20 以内但数据值域可以随机拉大一些这样才能触发 long long 溢出或单调性判断问题。我自己的调试经验是while (true) { 随机生成 n 和所有 C[i]; 跑一遍暴力 DP得到 ans1; 跑一遍 CHT得到 ans2; 如果 ans1 ! ans2输出这组数据人工分析; }这个流程看着笨实际排查效率比盯代码高十倍。遇到 CHT 题目卡壳不要干瞪眼先跑对拍。最后再分享一个小技巧我个人在实际使用中很少硬背 bad 函数的推导过程画图才是最快的。每次不确定公式方向时拿三条斜率递减的直线标出交点看你维护的“包络线”应该长什么样再回头推公式基本不会错。理解 CHT 的几何意义比记住代码模板重要得多。代码模板背得再熟方向一错就是整道题白写。希望这篇能帮你把凸包优化这层窗户纸捅破做题时少走点弯路。