斜率优化 DP

斜率优化 DP 的原理与实现：凸壳维护与单调队列优化。

  • 动态规划
  • 斜率优化
  • 凸包优化
  • 单调队列

一句话算法

斜率优化 DP 是把“枚举上一个决策点”变成“在凸包上找一条最优直线”。

问题模型

很多 DP 会出现这样的转移：

dp[i]=min⁡0≤j<i{dp[j]+(Ai−Aj−C)2} dp[i]=\min_{0\le j<i}\{dp[j]+(A_i-A_j-C)^2\}

其中：

  • ii 是当前状态；
  • jj 是上一个决策点；
  • AiA_i 是前缀量；
  • CC 是常数。

朴素做法要枚举所有 jj，时间复杂度是 O(n2)O(n^2)。当 AiA_i 单调递增时，可以用斜率优化把它降到 O(n)O(n)。

典型例题是 luogu-P3195。设：

Si=∑k=1ick,Ai=Si+i S_i=\sum_{k=1}^{i} c_k,\qquad A_i=S_i+i

把第 j+1j+1 到第 ii 个物品装在同一行的代价是：

(Ai−Aj−L−1)2 (A_i-A_j-L-1)^2

于是有：

dp[i]=min⁡0≤j<i{dp[j]+(Ai−Aj−L−1)2} dp[i]=\min_{0\le j<i}\{dp[j]+(A_i-A_j-L-1)^2\}

边界是：

dp[0]=0,A0=0 dp[0]=0,\qquad A_0=0

核心直觉

把式子展开，令：

Bi=Ai−L−1 B_i=A_i-L-1

则：

dp[i]=min⁡j<i{dp[j]+(Bi−Aj)2}=Bi2+min⁡j<i{dp[j]+Aj2−2BiAj} \begin{aligned} dp[i] &=\min_{j<i}\{dp[j]+(B_i-A_j)^2\}\\ &=B_i^2+\min_{j<i}\{dp[j]+A_j^2-2B_iA_j\} \end{aligned}

对固定的 ii，BiB_i 是常数。每个 jj 可以看成一个点：

Xj=Aj,Yj=dp[j]+Aj2 X_j=A_j,\qquad Y_j=dp[j]+A_j^2

转移里需要最小化的是：

Yj−2BiXj Y_j-2B_iX_j

这就是在所有点 (Xj,Yj)(X_j,Y_j) 中，找一个点让斜率固定的直线截距最小。

如果这些点按 XX 单调加入，并且查询斜率也单调变化，那么只需要维护下凸壳。队首就是当前最优决策点。

几何模型

对一个点 (Xj,Yj)(X_j,Y_j)，代入：

Yj−kXj Y_j-kX_j

可以理解为斜率为 kk 的直线经过这个点时的截距。本文的 k=2Bik=2B_i。

当 kk 单调增加时，最优点会沿着下凸壳从左往右移动，不会回头。因此可以用队列维护候选点：

  • 队首：当前查询最可能使用的决策点；
  • 队尾：新点加入时维护凸壳形状。

算法步骤

  1. 计算前缀量 Ai=Si+iA_i=S_i+i。
  2. 初始化 dp[0]=0，把点 0 放入队列。
  3. 对每个 i=1..n：
    • 当队首第二个点比队首更优时，弹出队首；
    • 用队首决策点计算 dp[i]；
    • 把新点 i 加入队尾；
    • 如果队尾中间点不再可能成为答案，弹出它。

队首如何弹出

设当前查询是 ii。若：

Yq2−2BiXq2≤Yq1−2BiXq1 Y_{q_2}-2B_iX_{q_2}\le Y_{q_1}-2B_iX_{q_1}

说明第二个候选点已经不差于第一个候选点。因为后续 BiB_i 单调递增，第一个点以后也不会再变优，可以弹出。

队尾如何维护凸壳

设队尾两个点是 a,ba,b，新点是 cc。如果：

Yb−YaXb−Xa≥Yc−YbXc−Xb \frac{Y_b-Y_a}{X_b-X_a}\ge \frac{Y_c-Y_b}{X_c-X_b}

说明斜率没有递增，点 bb 不在下凸壳上，应当删除。

为了避免浮点误差，代码中使用交叉相乘：

(Yb−Ya)(Xc−Xb)≥(Yc−Yb)(Xb−Xa) (Y_b-Y_a)(X_c-X_b)\ge (Y_c-Y_b)(X_b-X_a)

算法证明

关键不变量： 队列中的点按 XX 递增，并且相邻点之间的斜率严格递增。

  1. 队尾删除保证凸壳正确

    如果 a,b,ca,b,c 三点满足：

    slope(a,b)≥slope(b,c) slope(a,b)\ge slope(b,c)

    那么 bb 位于下凸壳上方或共线中间位置。无论查询斜率是多少，最优点都可以由 aa 或 cc 替代，bb 不可能成为唯一最优点。

  2. 队首删除不丢答案

    查询斜率随 ii 单调增加。若当前斜率下，第二个点已经不差于第一个点，那么在更大的斜率下，最优点只会继续向右移动，第一个点不会重新成为答案。

  3. 每个点最多进出一次

    每个状态 ii 生成一个点，只会从队尾进入一次；失效后从队首或队尾弹出一次。队列始终保存所有可能成为未来最优决策的点。

因此，每次使用队首计算得到的决策点都是当前最优决策点，DP 转移正确。

复杂度分析

每个点最多入队一次、出队一次。

  • 时间复杂度：O(n)O(n)。
  • 空间复杂度：O(n)O(n)。

如果查询斜率不单调，但点仍然可以组成凸壳，则通常需要在凸壳上二分，复杂度变为 O(nlog⁡n)O(n\log n)。

代码实现

cpp 
        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82

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

using i128 = __int128_t;

string to_string_i128(i128 x) {
    if (x == 0) return "0";
    bool negative = x < 0;
    if (negative) x = -x;

    string s;
    while (x > 0) {
        s.push_back(char('0' + x % 10));
        x /= 10;
    }
    if (negative) s.push_back('-');
    reverse(s.begin(), s.end());
    return s;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    long long L;
    cin >> n >> L;

    vector<long long> prefix(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        long long c;
        cin >> c;
        prefix[i] = prefix[i - 1] + c;
    }

    vector<long long> x(n + 1, 0);
    vector<i128> dp(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        x[i] = prefix[i] + i;
    }

    auto b = [&](int i) -> long long {
        return x[i] - L - 1;
    };

    auto y = [&](int j) -> i128 {
        return dp[j] + (i128)x[j] * x[j];
    };

    auto value = [&](int j, int i) -> i128 {
        return y(j) - (i128)2 * b(i) * x[j];
    };

    auto bad = [&](int a, int mid, int c) -> bool {
        return (y(mid) - y(a)) * (x[c] - x[mid]) >=
               (y(c) - y(mid)) * (x[mid] - x[a]);
    };

    deque<int> q;
    q.push_back(0);

    for (int i = 1; i <= n; ++i) {
        while (q.size() >= 2 && value(q[1], i) <= value(q[0], i)) {
            q.pop_front();
        }

        int j = q.front();
        dp[i] = (i128)b(i) * b(i) + value(j, i);

        while (q.size() >= 2 && bad(q[q.size() - 2], q[q.size() - 1], i)) {
            q.pop_back();
        }
        q.push_back(i);
    }

    cout << to_string_i128(dp[n]) << '\n';
    return 0;
}

测试用例

输入：

4 6
3
1
2
2

输出：

2

解释：

  • 把前两个物品放一行，长度为 3+1+1=53+1+1=5，代价 (5−6)2=1(5-6)^2=1；
  • 把后两个物品放一行，长度为 2+1+2=52+1+2=5，代价 (5−6)2=1(5-6)^2=1；
  • 总代价为 22。

应用分类详解

斜率优化 DP 的本质是优化形如“当前状态枚举历史决策点，并且交叉项可以拆成 X(j)⋅K(i)X(j)\cdot K(i)”的转移。

一、一维二次式 DP

典型模式： 转移中出现平方项，例如 (Ai−Aj−C)2(A_i-A_j-C)^2。

识别信号： 展开后能得到 Aj2−2AiAjA_j^2-2A_iA_j 这类交叉项。

核心建模： 把 jj 变成点 (Xj,Yj)(X_j,Y_j)，把 ii 变成查询斜率。

应用场景 经典题目 核心思路
玩具装箱 luogu-P3195 展开平方项，用下凸壳维护决策点
批处理分组代价 通用模型 分组代价是前缀量差的二次函数

二、线性函数取最值

典型模式： 转移可以整理成：

dp[i]=B(i)+min⁡j{Y(j)+K(i)X(j)} dp[i]=B(i)+\min_j\{Y(j)+K(i)X(j)\}

识别信号： 对固定 ii，jj 的贡献是一条直线或一个点的线性表达式。

核心建模： 每个历史决策是一条线或一个点，查询就是在某个横坐标/斜率下取最小值。

应用场景 经典题目 核心思路
Convex Hull Trick 动态规划优化模型 维护直线集合，查询最小值
斜率单调的 DP 本文模型 单调队列做到 O(n)O(n)

三、斜率不单调的变体

典型模式： 点能形成凸壳，但查询斜率不按顺序变化。

识别信号： 历史点按 XX 单调加入，但 K(i)K(i) 不单调。

核心建模： 仍维护凸壳，但查询时不能只弹队首，需要在凸壳上二分，或使用 Li Chao Tree。

应用场景 经典题目 核心思路
非单调斜率查询 通用 CHT 模型 凸壳二分或李超线段树
动态插线查询 函数最值维护 用 Li Chao Tree 维护直线集合

经典例题

1. luogu-P3195

斜率优化入门题。重点是把：

dp[j]+(Ai−Aj−L−1)2 dp[j]+(A_i-A_j-L-1)^2

展开成点和斜率的形式。

2. 批量任务分组 DP

若一段任务的代价是“前缀和差值的平方”，通常可以尝试同样的展开方式。

3. 直线集合最小值查询

当转移不是点的截距模型，而是多条直线在某个横坐标上的最小值时，本质仍是凸包优化。

参考