斜率优化 DP

一句话算法

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

问题模型

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

其中：

• $i$ 是当前状态；
• $j$ 是上一个决策点；
• $A_i$ 是前缀量；
• $C$ 是常数。

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

典型例题是 luogu-P3195。设：

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

于是有：

边界是：

核心直觉

把式子展开，令：

则：

对固定的 $i$，$B_i$ 是常数。每个 $j$ 可以看成一个点：

转移里需要最小化的是：

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

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

几何模型

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

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

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

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

算法步骤

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

队首如何弹出

设当前查询是 $i$。若：

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

队尾如何维护凸壳

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

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

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

算法证明

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

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

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

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

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

2. 队首删除不丢答案

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

3. 每个点最多进出一次

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

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

复杂度分析

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

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

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

代码实现

        
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;
}
    

        
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

        # 斜率优化 DP（玩具装箱）：dp[i] = min_{j<i} dp[j] + (x[i] - x[j] - L - 1)^2，x[i] = prefix[i] + i。
# 输入：第一行 n L；随后 n 个物品长度 c_i（n >= 1）。输出：dp[n]。
# 叉积比较全用 Python 任意精度整数，因此不需要 C++ 里的 __int128。
import sys
from collections import deque


def main() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    L = next(data)

    prefix = [0] * (n + 1)
    for i in range(1, n + 1):
        prefix[i] = prefix[i - 1] + next(data)

    # x[i] 是决策点的横坐标，因为 c_i >= 0 所以严格递增，保证凸壳斜率单调。
    x = [prefix[i] + i for i in range(n + 1)]
    dp = [0] * (n + 1)

    def b(i: int) -> int:
        return x[i] - L - 1

    def y(j: int) -> int:
        return dp[j] + x[j] * x[j]

    def value(j: int, i: int) -> int:
        # 把 (B_i - x[j])^2 展开后与 i 无关的截距部分：Y_j - 2 * B_i * X_j
        return y(j) - 2 * b(i) * x[j]

    def bad(a: int, mid: int, c: int) -> bool:
        # 叉积比较 slope(a, mid) >= slope(mid, c)，避免除法与浮点误差
        return (y(mid) - y(a)) * (x[c] - x[mid]) >= (y(c) - y(mid)) * (x[mid] - x[a])

    q = deque([0])  # 下凸壳，横坐标随入队递增；队首是当前最优决策点
    for i in range(1, n + 1):
        # 若第二个点已不劣于队首，由于 B_i 单调递增，队首以后也不会再变优
        while len(q) >= 2 and value(q[1], i) <= value(q[0], i):
            q.popleft()

        j = q[0]
        dp[i] = b(i) * b(i) + value(j, i)

        # 队尾三点若斜率不递增，则中间点永远不可能成为最优决策，弹出
        while len(q) >= 2 and bad(q[-2], q[-1], i):
            q.pop()
        q.append(i)

    print(dp[n])


if __name__ == "__main__":
    main()
    

测试用例

输入：

4 6
3
1
2
2

输出：

2

解释：

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

应用分类详解

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

一、一维二次式 DP

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

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

核心建模： 把 $j$ 变成点 $(X_j,Y_j)$，把 $i$ 变成查询斜率。

二、线性函数取最值

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

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

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

三、斜率不单调的变体

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

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

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

经典例题

1. luogu-P3195

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

展开成点和斜率的形式。

2. 批量任务分组 DP

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

3. 直线集合最小值查询

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

参考

• 本目录旧草稿与图示：asymptote/
• P3195 玩具装箱 - 洛谷