引言
假设你在赛场上遇到一道经典的区间DP题，比如「股票交易」或「最大子段和」，暴力枚举所有状态时你的程序在n=5000时就TLE了。这时候，如果你能掌握斜率优化（Convex Hull Trick），就能把时间复杂度从O(n²)降到O(n log n)，轻松碾压90%的选手。今天我们就用「经典例题→数学原理→代码实现」三步带你彻底搞懂这个黑科技！
核心概念讲解
斜率优化的本质是利用决策点的凸性性质，通过维护一个下凸包来快速找到最优决策点。想象你在爬山，每一步都有多个可选路径（状态转移方程中的j），而你要找到当前高度最优的那条路径。如果这些路径形成一条凸包，那么最优解一定在凸包的某个切点上。
数学表达：
设状态转移方程为 $dp[i] = \min_j (a[j] + b[i-j])$，其中$a$和$b$满足特定条件（如$b$单调递增）。我们可以将问题转化为求直线$y=a[j]+b[k]$（$k=i-j$）中与点$(k, dp[k])$的交点。通过维护这些直线的下凸包，我们可以用二分快速找到最优$k$。
C++代码示例
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 7;
int q[N], dp[N]; // q:单调队列存储凸包上的点坐标
// 判断点q[i]是否在q[j]和q[j+1]之间形成的线段下方
bool check(int j, int i) {
long long x1 = q[j], y1 = dp[q[j]];
long long x2 = q[j+1], y2 = dp[q[j+1]];
return (y2 - y1) * (i - x1) >= (dp[i] - y1) * (x2 - x1);
}
int main() {
int n; cin >> n;
vector<int> a(n); for (auto& x : a) cin >> x;
q[0] = 0; dp[0] = 0; // 初始条件
for (int i = 1; i <= n; ++i) {
// 队头过期（超出转移范围）
while (q[0] < i - n) q[0]++;
// 维护单调队列（保证下凸性）
while (q.size() > 1 && check(q[q.size()-2], q[q.size()-1]))
q.pop_back();
int k = q.back(); // 最优决策点
dp[i] = dp[k] + a[i-k]; // 状态转移
// 加入新点(i, dp[i])
while (q.size() >= 2 &&
(long long)(dp[i] - dp[q[q.size()-2]]) * (i - q[q.size()-2]) >=
(long long)(dp[q[q.size()-1]] - dp[q[q.size()-2]]) * (i - q[q.size()-1]))
q.pop_back();
q.push_back(i);
}
cout << dp[n] << '\n'; // 输出答案
}
注释说明：
q是单调队列，存储的是决策点的索引（即j值）check()函数用于判断是否要弹出队尾（维护凸包性质）(long long)防止乘法溢出
算法分析
时间复杂度：每个元素最多入队和出队一次 → O(n)
空间复杂度：O(n)（队列存储）
适用场景：形如$dp[i]=\min_j (cost(j)+cost(i-j))$且$cost$满足斜率单调性的问题
局限性：需要预处理$cost$函数的性质（如斜率单调递增/递减）
经典例题
- 思路：定义$dp[i]$表示前$i$件物品的最大价值，转移时需要枚举最后一个选的物品$k$，用斜率优化加速决策过程
- 提示：先处理前缀和，再用斜率优化求最优区间
推荐练习
P2045 友好城市 （基础斜率优化，难度★）
P2724 [国家集训队]最长双回文串 （结合回文特性，难度★★★）
CF1108F The Minimum Number of Trees （进阶，需理解斜率优化与分治结合）
小结
斜率优化的核心思想是通过几何性质减少无效计算。掌握它后，你不仅能解决区间DP，还能应对更复杂的背包变种。下期我们将学习四边形不等式优化，同样是让O(n²)变快的神器！