动态规划写多了之后你早晚会遇到一类看着很头疼的转移方程dp[i] min_{ji}(dp[j] 某个同时带 i 和 j 的交叉项)。这种式子用普通的前缀和优化处理不了直接枚举 j 复杂度又是 O(n^2)数据量一上 10^5 就彻底卡死。Convex Hull Trick我后面直接简称 CHT也有叫凸包优化、斜率优化的就是专门用来收拾这种转移的。它的核心想法其实很朴素把每个决策 j 看成一条直线那么转移问题就变成了“在若干条直线里回答某个横坐标处的最小值或最大值”。只要这些直线的斜率和查询的横坐标满足一定的单调性就能用单调队列、二分甚至李超线段树把总复杂度压到 O(n) 或 O(n log n)。这篇文章我打算从最朴素的失败做法讲起把它的几何直觉、代码模板、一道经典的“玩具装箱”例题还有我踩过的几个坑一次说清楚。适合正在打算法竞赛、刷动态规划进阶题的朋友也适合平时写性能敏感型动态规划的工程师参考。1. CHT到底在解决什么一个典型dp困境1.1 先看一个“看着能做但怎么也做不快”的转移我先摆一个最常见的转移方程也是后面实战部分会用到的一个简化版dp[i] min_{0 j i} ( dp[j] ( sum[i] - sum[j] - L )^2 )其中sum[i]是前缀和L是一个给定常数。这个方程的结构在划分型dp里特别常见前 i 个元素的答案等于某个 j 之前的答案加上从 j1 到 i 这一段产生的代价。如果你直接写两层循环就是经典的 O(n^2)n 到 1e5 的时候需要跑 1e10 次操作基本等于不可用。为什么普通优化解决不了因为代价里的(sum[i] - sum[j] - L)^2一展开就会出现-2 * sum[i] * (sum[j] L)这种“i 的变量乘 j 的变量”的交叉项。这种交叉项意味着在不同 i 眼里同一个 j 的“性价比”是不一样的。它不像形如dp[j] cost[j]这种可以维护前缀最小值的东西j 对 i 的影响不是固定不变的。所以你需要换一种视角把每个 j 变成一个随 i 变化的函数然后回答 i 处的函数最小值。1.2 把决策j变成一条直线问题一下变简单了我们来做一点点数学展开公式不长但这一步是整个 CHT 的命根子。对固定的 j把代价部分拆开(sum[i] - sum[j] - L)^2 sum[i]^2 - 2 * sum[i] * (sum[j] L) (sum[j] L)^2代回原来的转移方程sum[i]^2这一项跟 j 完全无关可以直接提到 min 外面dp[i] min_j ( -2 * (sum[j] L) * sum[i] dp[j] (sum[j] L)^2 ) sum[i]^2仔细观察括号里的内容对于固定的 j它其实是一条关于变量x sum[i]的直线斜率m_j -2 * (sum[j] L)截距b_j dp[j] (sum[j] L)^2于是整个动态规划就变成了这样一件事每算完一个dp[i]就向一个“直线集合”里插入一条新直线每次要算dp[i]时就在这个集合里查询x sum[i]处的所有直线的最小值。这就是 Convex Hull Trick 的基本模型动态插入直线查询某横坐标处的最小值。2. 凸包优化的几何原理为什么答案藏在“下凸包”里2.1 一堆直线的下边界天然是一段下凸的折线想象你在坐标系里画出所有决策直线。对任意一个具体的x我们关心的是这些直线中最低的那个点。把所有 x 对应的最低点连起来你会得到一条分段线性的折线。这条折线在几何上就是这些直线构成的“下边界”也叫下包络。有个很关键的几何事实如果插入的直线斜率严格递增或递减那么这条折线一定是个下凸函数每一段都是某条直线的一部分。换句话说绝大多数直线在整个实数轴上根本不会被“轮到”它们完全被其他直线压在下面永远不可能是最优解。CHT 做的事情本质上就是维护这样一个下凸包丢弃那些注定没用的直线让查询时只需要看凸包上的一小部分直线而不是遍历所有决策。如果你做的是求最大值那对应的是上边界、上凸包原理完全对称只是比较符号反过来而已。本文下面默认讲最小值、下凸包因为这个方向最常用稍微改一下符号就能变成最大值版本。2.2 判断一条直线还有没有用从交点比较到点集凸包现在问题来了往凸包里插入一条新直线时怎么判断凸包末尾那条直线是否还有保留价值这里我必须强调一个很多教程都没讲清楚的坑网上流传的“比较两条直线交点横坐标”的写法在特定条件下是坑人的。最稳妥的判定方式是换个角度把直线y m*x b看成二维平面上的点(m, b)。可以证明一组直线的下包络对应这些点在以(m, b)为坐标的平面上的下凸包。于是当插入顺序是斜率递增已有最后两条直线是 l1、l2新直线是 l3判断 l2 是否应该被删除的条件就等价于判断点(m2, b2)是否落在了(m1, b1)与(m3, b3)连线的上方或线上(b2 - b1) * (m3 - m1) (b3 - b1) * (m2 - m1)为什么我推荐直接用这个式子而不是交点比较?因为“交点横坐标比较”的那个版本会让人忽略一个隐藏问题当新直线跨越两条旧直线直接成为凸包边界时末尾两条直线的交点信息可能是错的。我第一次写的时候就是用交点比较结果在小数据上对拍发现少删了一条直线卡了半天。用上面这个“点凸包”判定之后情况就稳定多了。注意这个式子里所有斜率差都是正的因为斜率递增所以可以直接交叉相乘不需要除以浮点数也不会出现除以零的问题。3. CHT的三种代码实现3.1 最基础的直线结构与bad函数先放一个所有实现共用的结构体很简单struct Line { long long m, b; // y m*x b long long eval(long long x) const { return m * x b; } }; // 判断 l2 是否可以被删除。适用于斜率严格递增、维护最小值下凸包的情况。 bool bad(const Line l1, const Line l2, const Line l3) { return (l2.b - l1.b) * (l3.m - l1.m) (l3.b - l1.b) * (l2.m - l1.m); }这里所有计算都用整数里的等号表示“即使三点共线也删掉中间那条”。删掉中间重复点的好处是凸包上不会有冗余查询逻辑更干净。如果你发现某些题卡边界可以改成再试但大多数时候用都不会出问题。3.2 指针扫描法斜率和查询点都单调O(n) 拿下最经典的一种使用场景插入的斜率单调且每次询问的横坐标 x 也单调递增。这时可以在凸包数组上维护一个head指针查询时直接往后走。因为 x 一直在增大最优直线在凸包上的位置只可能往后移动不会回退。vectorLine hull; int head 0; void add_line(Line nw) { while (hull.size() 2 bad(hull[hull.size() - 2], hull[hull.size() - 1], nw)) { hull.pop_back(); } hull.push_back(nw); } long long query(long long x) { while (head 1 (int)hull.size() hull[head].eval(x) hull[head 1].eval(x)) { head; } return hull[head].eval(x); }注意几个细节。第一个是head只增不减所以前提是查询的 x 必须单调不减否则你会查到错误的直线。第二个是插入和查询的顺序不能乱必须先把所有优先算出来的直线插好再去查询。第三个是hull初始时至少要有一条直线否则query会越界。很多题目 j 可以从 0 开始记得提前把j 0对应的直线插进去。3.3 二分查询法查询点任意O(n log n) 也够用很多题目里查询的 x 并不单调或者你不想维护head指针的方向。那就在凸包数组上二分。下凸包上的直线按斜率递增排列后对任意固定 x各条直线的取值是一个先递减后递增的单峰序列所以可以二分找最小值点long long query(long long x) { int l 0, r (int)hull.size() - 1; while (l r) { int mid (l r) / 2; if (hull[mid].eval(x) hull[mid 1].eval(x)) { r mid; } else { l mid 1; } } return hull[l].eval(x); }这个写法在x单调、不单调的情况下都能用只是复杂度从均摊 O(1) 变成了每次 O(log n)。如果你只熟悉指针扫描二分法也可以作为验证正确性的对照实现。实际上我在对拍时经常两个版本互相验证能抓出不少细节问题。3.4 扩展李超线段树应对乱序插入如果插入的斜率不单调甚至插入顺序乱掉单调队列就完全没法用了。这时候可以考虑李超线段树它本质上是在线段树节点上维护“在当前区间里最优的直线”插入一条直线时递归比较查询时把路径上所有节点存的直线都取一遍最小值。李超树的核心思想是“区间淘汰”每条直线只会有贡献的那段横坐标区间里保留插入时沿着线段树递归每次只往一边下降。复杂度是 O(log C) 插入、O(log C) 查询其中 C 是横坐标的值域。这个结构写起来也不复杂但代码会比单调队列长不少。对于初学者我建议先把单调队列和二分版本吃透李超树作为进阶储备。4. 实战玩具装箱从推导到AC4.1 题目模型与状态设计拿一个非常经典的题来完整走一遍流程有 n 个玩具第 i 个的长度是c[i]。要把它们按顺序装箱每箱可以装连续的一段。如果第 i 到第 j 个玩具装在同一箱箱子长度定义为这段玩具的数量加上它们长度之和。每个箱子的费用是(箱子长度 - L)^2其中 L 是给定的常数。求装完所有玩具的最小总费用。设s[i]为长度前缀和dp[i]表示前 i 个玩具装完的最小费用。转移方程就是dp[i] min_{0 j i} ( dp[j] ( (i - j - 1) (s[i] - s[j]) - L )^2 )令a[i] s[i] i - 1 - Lb[j] s[j] j方程可以化简成dp[i] min_j ( dp[j] (a[i] - b[j])^2 )展开后就变成了我们熟悉的形式dp[i] min_j ( -2 * b[j] * a[i] dp[j] b[j]^2 ) a[i]^24.2 斜率取反的小技巧这里有个稍微烦人的点原式中斜率m_j -2 * b[j]是随 j 递减的而我们上面的模板要求斜率递增。解决办法很简单把直线斜率和查询点一起取反。我们不用m_j -2*b[j]和x a[i]而是用m 2*b[j]和x -a[i]两者的乘积是完全一样的(-2*b[j]) * a[i] (2*b[j]) * (-a[i])这样新的斜率m 2*b[j]严格递增插入时可以放心用之前的 bad 函数。查询点x -a[i]随 i 递增会严格递减虽然不满足指针扫描的方向但用 3.3 节的二分查询完全没问题复杂度 O(n log n)对 1e5 的数据量非常轻松。4.3 完整代码与关键注释#include bits/stdc.h using namespace std; struct Line { long long m, b; long long eval(long long x) const { return m * x b; } }; bool bad(const Line l1, const Line l2, const Line l3) { return (l2.b - l1.b) * (l3.m - l1.m) (l3.b - l1.b) * (l2.m - l1.m); } long long query(const vectorLine hull, long long x) { int l 0, r (int)hull.size() - 1; while (l r) { int mid (l r) / 2; if (hull[mid].eval(x) hull[mid 1].eval(x)) r mid; else l mid 1; } return hull[l].eval(x); } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; long long L; cin n L; vectorlong long s(n 1, 0); for (int i 1; i n; i) { long long c; cin c; s[i] s[i - 1] c; } vectorlong long dp(n 1, 0); vectorLine hull; // j 0 对应的直线: m 2*(s[0]0) 0, b dp[0] (s[0]0)^2 0 hull.push_back({0, 0}); for (int i 1; i n; i) { long long a s[i] i - 1 - L; long long xQuery -a; // 取反后的查询点 dp[i] query(hull, xQuery) a * a; // j i 的直线算完 dp[i] 再插入 long long b s[i] i; Line nw {2 * b, dp[i] b * b}; while (hull.size() 2 bad(hull[hull.size() - 2], hull[hull.size() - 1], nw)) { hull.pop_back(); } hull.push_back(nw); } cout dp[n] \n; return 0; }这段代码我已经用随机小数据和暴力 dp 对拍过很多次可以直接当模板用。有一点提醒一下a * a和b * b在最坏情况下可能到 1e12 量级再乘上 x 的 1e5 量级乘积可能突破 1e17所以所有涉及乘法的中间量都要用long long。如果题目给的数据范围更极限建议用__int128算完再转回long long。5. 常见问题与排查技巧5.1 交叉相乘时的不等号方向反了这个是我见过的最高频错误。bad 函数里到底是还是取决于你维护的是最小值还是最大值、斜率递增还是递减。我自己的经验是不要在头脑里推永远用“点 (m, b) 的下凸包”这个几何模型去判断。每次写完代码构造三组直线样例跑一下确认被删掉的那条确实完全不会成为最优解比你对着符号纠结十分钟有效得多。5.2 斜率相同的直线必须预处理如果两条直线斜率完全一样bad 函数的叉积会变成零判断结果可能不对。正确做法是在插入前合并求最小值时保留截距更小的那条求最大值时保留截距更大的那条。很多题目里决策点的斜率可能重复比如前缀和相等或者系数相同不处理的话凸包上会出现两条平行直线查询时虽然不至于 WA但会让凸包变得很脏增加调试难度。5.3 交点比较法为何不推荐网上很多 CHT 教程会写“比较新直线与队尾直线的交点和队尾与队首直线的交点横坐标”然后决定是否弹出队尾。这个写法在斜率递增且凸包结构完整的时候确实没错但有一个隐蔽的前提凸包内部相邻直线的交点横坐标必须严格递增。一旦出现新直线直接跨越两条旧直线直接成为新的边界仅仅比较相邻两个交点就会漏判。我实战中至少遇到两次这个问题后来干脆一律使用“点凸包判定”的 bad 函数彻底避免这类心智负担。5.4 对拍是调试 CHT 的救命稻草CHT 的调试难点在于你很难一眼看出凸包里哪条直线该删不该删。我的经验是写一个不超过 15 行的暴力 O(n^2)然后用随机数据生成器造一堆小规模数据暴力结果和 CHT 结果逐项比对。第一次写的人可能会觉得这样浪费时间但相信我符号错误、初始直线漏插、等号边界这类问题靠肉眼几乎看不出对拍能在几秒内告诉你错在哪组数据上。配合打印凸包里的直线斜率和截距你还能直观看到是哪一步删错了。6. 适用边界与我的实战经验6.1 什么样的 dp 能用 CHT我自己的判断标准是三部曲第一转移方程能写成dp[i] min_j(dp[j] f(i) * g(j) h(j)) h2(i)的结构也就是交叉项里 i 的部分和 j 的部分能完全分离开第二把 j 相关的项整理成直线(m_j, b_j)后斜率有单调性至少插入有序第三查询横坐标或者斜率二者至少有一个单调否则就需要上李超线段树。如果不满足第一点比如代价里同时出现i^2 * j这种高次项CHT 就帮不上忙了。6.2 与其他dp优化方法怎么选我身边经常有人把 CHT 和四边形不等式优化、wqs 二分混在一起。它们解决的问题不完全一样。四边形不等式优化适合代价函数满足四边形不等式的区间划分题通常也是优化到 O(n log n) 或 O(n^2) 降 O(n log n) 这类效果但不需要整理成直线判断条件也更独立。wqs 二分则擅长处理“恰好分 k 段”的带数量限制问题它经常和 CHT 一起用外层二分一个惩罚值内层用 CHT 求最优分段。如果你发现题目要求一段数恰好等于某个值不要慌先考虑能不能把数量限制用 wqs 二分转换成普通最小化问题再用 CHT 秒杀内层。6.3 我踩过最深的几个坑最后分享几条实战心得。第一最开始插入直线时别忘了j 0这个决策。很多题要求段可以从第一个元素开始如果不先插入空段对应的直线第一个dp[i]就会查不到值。第二二分查询里和的区别会影响结果取左还是取右对应着“删除中间直线时等号保留还是删除”。在多数题里用找最靠左的最优点比较稳。第三如果你发现跑出来是负数而且离谱地小多半是long long溢出了先检查所有乘法是不是都可能在 1e18 以上。第四写模板时最好把 bad 函数的参数顺序固定下来习惯性写成bad(hull[sz - 2], hull[sz - 1], nw)不要反过来否则符号判断全乱套。我个人在实际做题时的习惯是先不管点单不单调一律先用“斜率递增 二分查询”这个版本。等题目 AC 之后再根据输入数据的单调性优化成指针扫描版。原因很简单二分版对查询点的单调性零要求写起来不容易错指针扫描版虽然常数小但一旦 x 不是单调递增debug 的代价远超那点性能收益。另外我包里常备一份“玩具装箱”的 AC 代码当测试基准每次新写 CHT 模板的时候先跑一遍它再跑一遍随机对拍确认模板没被我改坏。这个方法帮我省掉了非常多无意义的排查时间建议你也试试。