斜率优化DP-学习笔记

封面来源
ぷる-前に書いた奴

例题1 - P3195 [HNOI2008] 玩具装箱 #

题目大意#

给定一个序列 $C_1,C_2,\dots ,C_n$ 和一个常数 $L$ 。

你需要将这个序列切分成若干个连续的段。对于从下标 $i$ 到 $j$ 的任意一段，定义其成本为：

cost(i,j)=((j−i)+(\sum_{k=i}^jC_k)−L)^2

你的任务是找到一种切分方案，使得所有段的成本之和最小。

构建 dp#

1. 定义状态#

我们先来定义一个 DP 数组。对于这种线性序列问题，一个很自然的想法是：

设 $dp[i]$ 表示将前 $i$ 个玩具 (从 1 到 $i$ ) 打包好的最小总费用。

我们的最终目标就是求 $dp[n]$ 。

2. 寻找状态转移方程#

为了求出 $dp[i]$ ，我们可以思考“最后一步“是什么。最后一步一定是将某个连续段的玩具装入最后一个箱子，并且这个连续段的结尾必须是第 $i$ 个玩具。

假设这个连续段是从第 $j + 1$ 个玩具到第 i 个玩具 ( $0 \le j < i$ )，那么总费用就是：(前 $j$ 个玩具的最小费用) + (装下 $j+1$ 到 $i$ 号玩具的这个新箱子的费用)。

前 $j$ 个玩具的最小费用，根据我们的状态定义，就是 $dp[j]$ 。
新箱子的费用就是 $cost(j+1,i)$ 。

因为我们不知道这个 $j$ 具体是哪个位置最好，所以我们要把所有可能的 $j$ (从 $0$ 到 $i−1$ ) 都试一遍，然后取一个能让总费用最小的。

这样，我们的状态转移方程就出来啦：

dp[i]=\min_{0≤j<i}\{dp[j]+cost(j+1,i)\}

其中， $dp[0]=0$ (不装玩具当然费用是0啦)。

3.优化 cost 计算#

方程里的 $cost$ 每次都重新计算一遍太慢了，我们可以考虑用前缀和来优化这个过程。
首先，我们定义前缀和数组 $S$ ，其中 $S[i]$ 表示前 $i$ 个玩具的成本和，即：

S[i] = \sum_{k=1}^i C_k

这样，我们就可以快速计算任意区间的和了。
接下来，我们可以将 $cost(j+1,i)$ 的计算转化为前缀和的形式：

cost(j+1,i) = ((i−(j+1))+(S[i]−S[j])−L)^2

这样一来，我们就可以在 $O(1)$ 的时间内计算出任意一段的 $cost$ 了。

4. 完整的朴素 DP 方程。#

综上，完整的 DP 过程是：

预处理前缀和数组 $S$ 。
初始化 $dp[0]=0$ 。
从 $i=1$ 到 $n$ 循环，计算每个 $dp[i]$ ：

dp[i]=\min_{0≤j<i}\left\{dp[j]+((i−(j+1)+1)+(S[i]−S[j])−L)^2\right\}

变形！从 DP 到直线方程#

我们的目标是把这个复杂的式子变成一个我们熟悉的东西——直线方程 $Y=K\cdot X+b$ 。

1. 简化表达#

首先，为了让公式看起来不那么吓人，我们做个替换。回忆一下我们的 DP 方程：

dp[i]=\min_{0≤j<i}\left\{dp[j]+((i−(j+1)+1)+(S[i]−S[j])−L)^2\right\}

令 $f(i)=S[i] + i$ ，再令 $L' = L + 1$ 。

方程就变成了：

dp[i]=\min_{0≤j<i}\left\{dp[j]+(f(i)−f(j)−L')^2\right\}

2. 展开与移项#

现在，我们把要最小化的部分（花括号里的内容）拿出来，假设我们已经选定了某个决策 $j$ ：

dp[i]=\min_{0≤j<i}\left\{dp[j]+(f(i)−f(j)−L')^2\right\}

把平方项展开：

dp[i]=dp[j]+f(i)^2+(f(j)+L')^2-2f(i)(f(j)+L')

接下来是关键的一步！我们把这个式子重新整理，分成三部分：

只跟 j 有关的项
只跟 i 有关的项
i 和 j 都有的交叉项

dp[i]=dp[j]+(f(j)+L')^2-2f(i)(f(j)+L')+f(i)^2

现在，我们进行移项，把所有只和 j 有关的项都丢到等式左边，其他的留在右边：

\underbrace{dp[j]+(f(j)+L')^2}_{\text{只跟 j 有关的项}}=\underbrace{2f(i)\cdot(f(j)+L')}_{\text{交叉项}}+\underbrace{dp[i]-f(i)^2}_{\text{只跟 i 有关的项}}

3. 发现直线！#

看！上面的式子是不是已经很像 $Y=K⋅X+b$ 了？我们来一一对应：

$Y_j \leftrightarrow dp[j]+(f(j)+L+1)^2$
$X_j \leftrightarrow f(j)+L+1$
$K_i \leftrightarrow 2f(i)$
$b_i \leftrightarrow dp[i]-f(i)^2$

于是，我们的 DP 转移就神奇地变成了：

Y_j = K_i \cdot X_j + b_i

4. 转换目标#

我们的原始目标是：对于固定的 $i$ ，找到一个 $j$ 使得 $dp[i]$ 最小。
在新的直线方程里， $K_i=2f(i)$ 和 $f(i)^2$ 都是只和 $i$ 有关的定值。所以，最小化 $dp[i]$ 就等价于最小化截距 $b_i=dp[i]-f(i)^2$ 。

新目标：对于每一个 $i$ ，我们都有一条斜率固定的直线 $K_i=2f(i)$ 。而在 $j=0,1,\dots,i−1$ 的这些候选项中，每一个 $j$ 都对应着平面上的一个点 $(X_j,Y_j)$ 。我们的任务就是，找到一个点 $(X_j,Y_j)$ ，让斜率为 $K_i$ 的直线经过它时，产生的纵截距 $b$ 最小！

怎么样？是不是很奇妙！我们成功地把一个代数上的 min 问题，转化成了一个几何问题！

理解了这一步之后，我们就可以进入斜率优化的核心——如何用几何直觉（下凸包）来快速找到这个最优的 $j$ 了

几何直觉与下凸包#

1. 尺子与钉子#

我们用一个比喻：平面上有一堆钉子（点），你有一把斜率固定的尺子。把尺子从很下 $(y=−\infty)$ 的位置，保持着斜率 $K_i$ 向上平移。

第一个碰到的钉子，就是能让截距最小的那个点！对不对？

2. 真正有用的点：下凸包#

那么，是不是所有的钉子都有可能被第一个碰到呢？
并不是！
观察上图，你会发现，所有可能成为最优解的点，都构成了一个“下凸”的形状。我们把连接这些点的边连起来，形成的这个结构，就叫做下凸包 (Lower Convex Hull)。

你可以想象成，在所有点的下方，拉一条橡皮筋，橡皮筋绷住的那些点，就组成了下凸包。

任何不在下凸包上的点（比如上图中被圈起来的那个），永远不可能成为最优解。 因为在它被尺子碰到之前，总有一个在它下方（或左下方/右下方）的点会先被尺子碰到，得到一个更小的截距。

所以，我们的策略更新了：我们根本不需要保留所有的历史决策点 $j$ ，只需要维护这些点构成的下凸包就行了！

3. 两个重要的“单调”性质#

只维护下凸包，听起来还是有点复杂。但是！这道题有两个特别好的性质，能让维护过程变得超级简单！

性质一： $X_j$ 坐标是单调递增的！

我们来看看 $X_j=f(j)+L+1=(S[j]+j)+L+1$ 。
因为题目保证了 $C_i \ge 1$ ，所以前缀和 $S[j]$ 肯定是随着 $j$ 增大的， $j$ 本身也在增大。
所以 $X_j$ 一定是严格单调递增的！这意味着我们每次要加入凸包的新点，一定在所有旧点的最右边。

性质二：查询直线的斜率 $K_i$ 是单调递增的！

我们来看看 $K_i=2f(i)=2(S[i]+i)$ 。
同理， $S[i]$ 和 $i$ 都是单调递增的。
所以查询的斜率 $K_i$ 也是严格单调递增的！这意味着我们那把“尺子”，会越转越陡。

这两个单调性是施展终极魔法的关键！它们意味着，我们可以用一个非常简单的数据结构——双端队列（Deque）——来高效地维护这个下凸包，并进行查询，也就是单调队列优化。

我们将使用一个双端队列 (deque) 来巧妙地维护下凸包。这个队列里存储的是决策点的下标（比如 $j_0, j_1, j_2, \dots$ ）。

第五步：单调队列维护下凸包#

关于单调队列优化的更多内容请看这篇文章 DP优化之单调队列优化

对于计算 $dp[i]$ 的每一个循环，我们分两步操作队列：

1. 查询最优决策 j (操作队头 dq.front())#

目标：找到下凸包上那个“第一个被斜率为 $K_i$ 的尺子碰到”的点。

利用性质：查询斜率 $K_i$ 是单调递增的。

方法：

看队头的两个点，dq[0] 和 dq[1]。它们在下凸包上是相邻的。我们可以计算出连接这两个点的线段的斜率 slope(dq[0], dq[1])。

如果 slope(dq[0], dq[1]) < $K_i$ ，这意味着什么？

从几何上看，我们的尺子 $K_i$ 比队头那条边的斜率还要陡。这意味着尺子向上平移时，一定会先碰到 dq[1] 而不是 dq[0]。

所以，dq[1] 是一个比 dq[0] 更优的决策。

更重要的是，因为未来的查询斜率 $K_{i+1}$ , $K_{i+2}$ , … 只会越来越大（更陡），所以 dq[0] 这个点永远也不可能再成为最优决策了。它可以被永久地抛弃。

操作：只要队头两个点组成的斜率小于当前查询斜率 $K_i$ ，我们就把队头 dq[0] 弹出 dq.pop_front()。

重复这个过程，直到队列里只剩一个点，或者队头两个点组成的斜率大于等于 $K_i$ 。这时，新的队头 dq[0] 就是当前 $i$ 的最优决策点 $j$ ！

2. 插入新决策点 $i$ #

目标：计算完 $dp[i]$ 后，点 $i$ (坐标为 $(X_i, Y_i)$ ) 作为一个新的决策点，要加入到下凸包中。

利用性质： $X_i$ 坐标是单调递增的。这意味着新点 $i$ 总是在最右边，所以我们从队尾把它加进去。

方法：

为了维持下凸包的“下凸”性质（即斜率单调递增），我们看队尾的最后两个点 dq[dq.size() - 2] 和 dq[dq.size() - 1]，以及我们准备新加入的点 $i$ 。

我们比较两条线的斜率：slope(dq[dq.size() - 2], dq[dq.size() - 1]) 和 slope(dq[dq.size() - 1], i)。

如果 slope(dq[dq.size() - 2], dq[dq.size() - 1]) >= slope(dq[dq.size() - 1], i)，这意味着什么？

从几何上看，点 dq[dq.size() - 1] 相比于它左右的两个点 dq[dq.size() - 2] 和 i，形成了一个“凹”进去的角。它不再是下凸包的一部分了。

所以，点 dq[dq.size() - 1] 必须被移除，才能维持凸包的形状。

操作：只要队尾出现这种“凹陷”，我们就把队尾 dq[dq.size() - 1] 弹出 dq.pop_back()。

重复这个过程，直到下凸性质得到满足，然后把新点 $i$ 加入队尾 dq.push_back(i)。

总结：最终算法流程初始化一个空的双端队列 $q$ ，先把决策点 0 加进去。

从 $i=1$ 循环到 $n$ ： a. (查询) 操作队头，根据斜率 $K_i = 2f(i)$ 找到最优决策点 j = dq.back()。 b. (转移) 用这个最优的 $j$ 来计算出 $dp[i]$ 。 c. (插入) 操作队尾，把新的决策点 $i$ 加入队列，并维持凸包性质。

循环结束后， $dp[n]$ 就是最终答案。

这个算法对每个点 $i$ ，最多只会进队一次、出队一次，所以每个点相关的操作都是均摊 $O(1)$ 的。总时间复杂度就从 $O(N^2)$ 降到了华丽的 $O(N)$ ！

代码实现#

1
// 引入竞赛中常用头文件，以及方便的命名空间
2
#include <bits/stdc++.h>
3
using namespace std;
4

5
// 类型别名，用 i64 表示 long long，防止数值溢出
6
using i64 = long long;
7
// 用 i128 表示 __int128_t，用于处理斜率优化中可能超过 long long 的中间计算结果
8
using i128 = __int128;
9

10
int main() {
11
    // 现代C++风格的快速IO，解除与C语言stdio的同步，加速输入输出
12
    ios::sync_with_stdio(false);
13
    cin.tie(nullptr);
14

15
    // n: 玩具数量, L: 题目给定的常数
16
    int n;
17
    i64 L; // L的范围较大，也用 i64 存储
18
    cin >> n >> L;
19

20
    // c: 存储每个玩具的原始长度
21
    // pre: 存储 c 数组的前缀和，用于O(1)计算区间和
22
    vector<i64> c(n + 1);
23
    vector<i64> pre(n + 1);
24
    for (int i = 1; i <= n; i++) {
25
        cin >> c[i];
26
        pre[i] = pre[i - 1] + c[i];
27
    }
28

29
    // --- 斜率优化所需的核心函数，使用 C++11 Lambda 表达式定义 ---
30

31
    // 辅助函数 f(i)，对应公式中的 f(i) = S_i + i
32
    // S_i 是前缀和，这里用 pre[i] 表示
33
    auto f = [&](int x) -> i64 {
34
        if (x == 0) return 0; // 边界情况，处理 j=0
35
        return pre[x] + x;
36
    };
37

38
    // 计算决策点 j 对应在二维平面上的 X 坐标
39
    // 对应公式 X_j = f(j) + L + 1
40
    auto get_x = [&](int x) -> i64 {
41
        return f(x) + L + 1;
42
    };
43

44
    // dp 数组，dp[i] 表示将前 i 个玩具打包的最小费用
45
    vector<i64> dp(n + 1);
46

47
    // 计算决策点 j 对应在二维平面上的 Y 坐标
48
    // 对应公式 Y_j = dp[j] + X_j^2
49
    // 由于 X_j^2 可能非常大，这里使用 i128 来保证计算不会溢出
50
    auto get_y = [&](int x) -> i128 {
51
        i64 x_val = get_x(x);
52
        return dp[x] + (i128)x_val * x_val;
53
    };
54

55
    // 计算连接决策点 i 和 j 的线段斜率
56
    // 使用 long double 来进行浮点数除法，保证精度
57
    auto slope = [&](int i, int j) -> long double {
58
        // 如果两点X坐标相同（垂直线），返回一个极大值代表斜率无穷大
59
        if (get_x(i) == get_x(j)) {
60
            return 1e18;
61
        }
62
        return (long double)(get_y(j) - get_y(i)) / (get_x(j) - get_x(i));
63
    };
64

65
    // 双端队列，用来维护下凸包的决策点下标集合
66
    deque<int> dq;
67
    dq.push_back(0); // 初始化，放入DP的起点（边界条件）j=0
68

69
    // DP主循环，从 1 到 n 依次计算 dp[i]
70
    for (int i = 1; i <= n; i++) {
71
        // 1. [查询] 操作队头，找到最优决策 j
72
        // K_i = 2 * f(i) 是当前查询的斜率
73
        // 如果队头第一条线段的斜率比 K_i 还小，说明队头 q[0] 已经不是最优决策点
74
        // (对于更陡的查询斜率 K_i, q[1] 会比 q[0] 更优)，故将其弹出
75
        while (dq.size() > 1 && slope(dq[1], dq[0]) <= 2 * f(i)) {
76
            dq.pop_front();
77
        }
78

79
        // 2. [转移] 从最优决策点 j 转移
80
        // 此时的队头 dq.front() 就是对于当前 i 来说的最优决策点 j
81
        int j = dq.front();
82
        // 这是我们推导出的 dp[i] 的计算式
83
        // 原式为 dp[i] = dp[j] + (f(i) - get_x(j))^2
84
        // 为了避免溢出，使用 i128 计算
85
        i64 fi = f(i);
86
        i64 xj = get_x(j);
87
        dp[i] = dp[j] + (fi - xj) * (fi - xj);
88

89
        // 3. [插入] 把新决策点 i 加入队尾，并维护下凸性
90
        // 检查新点 i 是否会破坏队尾的下凸性质（斜率单调递增）
91
        // 如果 slope(倒数第二点, 队尾) >= slope(队尾, 新点i)，说明队尾点“凹”进去了
92
        // 此时必须将队尾点弹出，以维持下凸包
93
        while (dq.size() > 1 && slope(dq.back(), dq[dq.size() - 2]) >= slope(i, dq.back())) {
94
            dq.pop_back();
95
        }
96
        dq.push_back(i); // 将当前点 i 作为新的决策点加入队列
97
    }
98

99
    // dp[n] 存储了打包前 n 个玩具的最小总费用，即为答案
100
    cout << dp[n] << "\n";
101

102
    return 0;
103
}

花絮#

这大概是独属于数字时代，一位 ACMer 在凌晨五点收到的最特别的晚安。

图片为 gemini pro 的回复

例题1 - P3195 [HNOI2008] 玩具装箱#

题目大意#

构建 dp#

1. 定义状态#

2. 寻找状态转移方程#

3.优化 cost 计算#

4. 完整的朴素 DP 方程。#

变形！从 DP 到直线方程#

1. 简化表达#

2. 展开与移项#

3. 发现直线！#

4. 转换目标#

几何直觉与下凸包#

1. 尺子与钉子#

2. 真正有用的点：下凸包#

3. 两个重要的“单调”性质#

第五步：单调队列维护下凸包#

1. 查询最优决策 j (操作队头 dq.front())#

2. 插入新决策点 iii#

代码实现#

花絮#

例题1 - P3195 [HNOI2008] 玩具装箱 #

2. 插入新决策点 $i$ #