斜率优化DP：把状态转移变成“找直线”

这是什么，用来干什么？

动态规划有时候会遇到这样的转移方程：

dp[i] = min(dp[j] + 某种与 i、j 都有关的代价)

如果这个代价能写成 a[i] * b[j] + c[j] 的形式，那么我们可以把每个 j 看作一条直线 y = k * x + b，其中 k 和 b 由 j 决定，而 x 由当前 i 决定。要找 dp[i]，就是在这些直线里，找当 x 等于某个值时 y 最小的那条直线。如果你把很多条直线画在坐标系里，它们会形成一个“凸包”（下凸壳）。再利用斜率单调的特点，可以用单调队列快速找到最优直线，时间从 O(n²) 降到 O(n)。这就是 斜率优化。

分步理解：从公式到几何

1. 一个具体例子：跑步机关卡

原题：dp[j] = min(dp[i] + (x[j] - x[i])²)，其中 x 是递增的位置。

展开一下：

dp[j] = min(dp[i] + x[j]² - 2 * x[i] * x[j] + x[i]²)
      = min( (-2 * x[i]) * x[j] + (dp[i] + x[i]²) ) + x[j]²

注意最后那个 x[j]² 跟 i 无关，可以提出来。现在对于固定的 j，我们只需要求：

min( (-2 * x[i]) * x[j] + (dp[i] + x[i]²) )

把 -2 * x[i] 看作斜率 k，dp[i] + x[i]² 看作截距 b，那么每个 i 对应一条直线 y = k * x + b。当 x = x[j] 时，这条直线的 y 值就是候选的 dp[j] 的一部分。

2. 生活比喻：买铅笔

假设学校门口有好几家文具店，每家店卖铅笔的价格是：单价 = 基础价 + 折扣 × 你买的数量。你想买 n 支铅笔，想花最少的钱。每家店的价格可以写成一条直线：总价 = 单价 × 数量。如果你知道每家店的单价函数，那么对于每个数量，你只需要找最便宜的那家店。如果单价随数量单调变化，你需要维护一个“最好的店”的集合——这就是凸包。

3. 怎么找最优直线？——凸包和单调队列

我们把所有可能的直线（对应历史决策 i）画出来，你会发现：真正有用的 直线只会是那些“下凸包”上的直线。比如下图：

y
↑
|   Line3
|  /
| /  Line2
|/  Line1
+--------→ x

Line1 和 Line3 是凸包的一部分，Line2 被完全压在里面，永远不会成为最优。判断一条直线是否被淘汰，要看它与前后两条直线的交点顺序。如果新直线与倒数第二条直线的交点，比倒数第二条与前一条直线的交点更靠左（或更靠右，取决于斜率单调方向），那么最后一条直线就永远用不上了，可以删掉。

因为 x 是单调递增的（题目保证），最优直线的位置只会逐渐向右移动，所以我们可以用双端队列（deque）来维护凸包。每一步：

从队头弹出那些在当前位置 x 已经不如第二条直线优的直线；
拿队头直线计算 dp[i]；
把新直线加入队尾，同时维护凸包性质。

新手容易犯的错误

忘记检查分母为零：求两条直线交点时，如果斜率相等（k1 == k2），会导致分母为零。实际中斜率一般不会完全相等，但整数运算时可能因为整除导致精度问题。安全做法是写成 double 并用交叉相乘避免除法。
整数除法精度：相交坐标 (b2 - b1) / (k1 - k2) 如果用整数除法会向下取整，导致凸包判断出错。必须使用 double 或 long double。
初始化遗忘了第一条直线：在循环开始前，需要把第一个决策（i=0）对应的直线加入队列。很多人会忘记，导致第一个状态计算错误。
比较符号搞反：求最小值时用下凸壳，队头弹出条件应该是 dq[0].value(x) >= dq[1].value(x)；求最大值用上凸壳，符号相反。很多同学把符号写反导致答案错误。
没有判断队列只有一条直线的情况：进行凸包维护时，要保证队列至少有两条直线才能比较交点，否则会越界。

完整可运行的示例代码

下面是一个完整的程序，输入一组递增的位置 x，输出从第 0 个点跑到第 n-1 个点的最小花费。代码中每行变量都加了中文注释，方便理解。

#include <iostream>
#include <deque>
#include <vector>
using namespace std;

typedef long long ll;

struct Line {
    ll k;   // 斜率
    ll b;   // 截距
    // 计算 y = k * x + b
    ll value(ll x) const {
        return k * x + b;
    }
    // 求两条直线交点的 x 坐标（浮点数）
    double intersect(const Line& other) const {
        // 注意：斜率不会相等，所以分母不为零
        return (double)(other.b - b) / (k - other.k);
    }
};

int main() {
    // 输入处理
    int n;
    cout << "请输入点的数量 n: ";
    cin >> n;
    vector<ll> x(n);   // 位置数组，必须严格递增
    cout << "请输入 " << n << " 个递增的位置 (x[0] < x[1] < ...): ";
    for (int i = 0; i < n; ++i) {
        cin >> x[i];
    }

    vector<ll> dp(n, 0);   // dp[i] 表示从0到i的最小花费
    deque<Line> dq;        // 存储凸包上的直线

    // 初始直线：从位置0出发，dp[0]=0，所以直线为 y = -2*x[0] * x + (dp[0] + x[0]^2)
    dq.push_back({-2 * x[0], dp[0] + x[0] * x[0]});

    for (int i = 1; i < n; ++i) {
        // 1. 弹出队头：当前查询点 x[i] 下，队头不如队头+1优
        while (dq.size() >= 2 && dq[0].value(x[i]) >= dq[1].value(x[i])) {
            dq.pop_front();
        }
        // 2. 计算 dp[i]
        dp[i] = dq[0].value(x[i]) + x[i] * x[i];
        // 3. 插入新直线：对应决策 i
        Line newLine = {-2 * x[i], dp[i] + x[i] * x[i]};
        // 4. 维护凸包：删除无用的队尾直线
        while (dq.size() >= 2) {
            Line last1 = dq[dq.size() - 2];
            Line last2 = dq.back();
            // 如果新直线与 last2 的交点 <= last2 与 last1 的交点，则 last2 被淘汰
            if (last1.intersect(last2) >= last2.intersect(newLine)) {
                dq.pop_back();
            } else {
                break;
            }
        }
        dq.push_back(newLine);
    }

    cout << "最小花费: " << dp[n-1] << endl;
    return 0;
}

运行示例：

请输入点的数量 n: 5
请输入 5 个递增的位置 (x[0] < x[1] < ...): 0 2 5 8 10
最小花费: 100

你可以自己手算验证：(10-0)^2 = 100，确实是一步跨到终点最划算。

什么时候能用斜率优化？

总结一下，你的 DP 转移必须满足三个条件：

形式：dp[i] = min/max (a[i] * b[j] + c[j]) + d[i]
其中 a[i] 只与 i 有关，b[j]、c[j] 只与 j 有关，d[i] 只与 i 有关。
斜率单调：a[i]（即 x 的系数）随着 i 增大单调递增或递减。这样才能保证最优决策点单向移动。
交点单调：候选直线的交点横坐标必须是单调的，这样用单调队列才能正确维护。

如果你在竞赛中遇到类似 dp[i] = min(dp[j] + (sum[i] - sum[j])^2) 或 dp[i] = min(dp[j] + cost(j+1, i)) 且 cost 有某种线性性质，都可以考虑斜率优化。

斜率优化动态规划：用几何加速