困难C++7 分钟2,284 字

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

这是什么,用来干什么?

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

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];
  • 把新直线加入队尾,同时维护凸包性质。

新手容易犯的错误

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

完整可运行的示例代码

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

cpp
#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 转移必须满足三个条件:

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

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


相关指引

  • 凸包概念​​:可以先学习计算几何中的凸包,理解为什么只有凸包上的点有用。
  • 单调队列​​:斜率优化通常用单调队列维护,先掌握普通单调队列(滑动窗口)的用法。
  • 动态规划基础​​:熟练写出朴素 O(n²) 的 DP,再考虑优化。如果连朴素 DP 都写不出来,不要急着学斜率优化。
  • 其他优化技巧​​:四边形不等式优化、CDQ 分治、李超线段树,都是 DP 优化的好帮手。

斜率优化就像给 DP 装上了“透视眼”,能一眼看出哪条直线最棒。虽然初次接触有些抽象,但多做几道题(比如「玩具装箱」「土地购买」),你就能体会到用几何思维解 DP 的乐趣。加油!

同类知识点