企业官网建设流程全解析

动态规划写多了之后，你早晚会遇到一类看着很头疼的转移方程：dp[i] = min_{j<i}(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 之前的答案，加上从 j+1 到 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 一直在增大，最优直线在凸包上的位置只可能往后移动，不会回退。

vector<Line> 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. 实战：玩具装箱从推导到AC

4.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 - L，b[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]^2

4.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 vector<Line>& 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; vector<long long> s(n + 1, 0); for (int i = 1; i <= n; i++) { long long c; cin >> c; s[i] = s[i - 1] + c; } vector<long long> dp(n + 1, 0); vector<Line> 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 模板的时候先跑一遍它，再跑一遍随机对拍，确认模板没被我改坏。这个方法帮我省掉了非常多无意义的排查时间，建议你也试试。