算法简介：猫爪冻冻

这里我们讲的是斜率优化DP。需要用到较多的数学知识，算是 DP 优化中比较难的东西了。这里会尽量的去把它讲详细起来。斜率优化 DP 从字面上来讲就是通过斜率优化这个DP算法。接下来就从一个斜率优化的入门例题讲解下来。

算法演示：猎人射术

例题选讲：猫尾隐藏菜单

大秦 为你打开 题目传送门

有 $N$ 个任务排成一个序列在一台机器上等待执行，它们的顺序不得改变。机器会把这 $N$ 个任务分成若干批，每一批包含连续的若干个任务。从时刻 $0$ 开始，任务被分批加工，执行第 $i$ 个任务所需的时间是 $T_i$ 。另外，在每批任务开始前，机器需要 $S$ 的启动时间，故执行一批任务所需的时间是启动时间 $S$ 加上每个任务所需时间之和。

一个任务执行后，将在机器中稍作等待，直至该批任务全部执行完毕。也就是说，同一批任务将在同一时刻完成。每个任务的费用是它的完成时刻乘以一个费用系数 $C_i$ 。

请为机器规划一个分组方案，使得总费用最小。

部分分 数值
第一档 $n\le5\times10^3,1\le t_i,c_i\le100$
第二档 $n\le10^4,1\le t_i,c_i\le100$
第三档 $n\le3\times10^5,0\le

例题解析：猫尾打烊之时

首先，我们一步一步来剖析这道题目。看向他的第一个数据点 $n \le 5\times10^3$ ，有点难评。。

不妨，先来点小菜开开胃，直接大力 $O(n^3)$ 试试。看见这种分成了一段一段的题目，我们不难直接想到了 $dp[i][j]$ 表示前 $i$ 个任务，分成了 $j$ 段这样的最小值作为状态。

那么，不难写出转移方程：
$$
dp[i][j] = \max_{0\le k\lt i} dp[k][j-1] + \left(\left(\sum\limits_{p=1}^{i}t_p\right) + s\times j\right)\times\sum\limits_{p=k+1}^{i}c_p
$$
这个式子就是代表了你找到了一个点 $k$ 前面的开了另一段，这样的花费。代码也非常的简单，就不放了。

接下来，我们就要考虑如何把他优化到 $O(n^2)$ 去 AC 这第一个部分分。首先为了方便阅读，我们首先把上边的转移方程式子用前缀和的形式表达出来。分别定义了数组 $sumt[i]$ 表示 $\sum\limits_{p=1}^i t_p$ ，$sumc$ 也是同理，即 $\sum\limits_{p=1}^i c_p$。那么原来的转移方程式子，就可以改写成：
$$
dp[i][j] = \min_{0\le k\lt i} dp[k][j-1] + \left(sumt[i] + s\times j\right)\times(sum[i]-sum[k])
$$
观察式子，发现 $j$ 的作用仅是为了计算此前个过程中的启动时间和，但事实上，既然这个时间要乘上此后的所有 $f$ ，不如提前加入其中。因为若分完前 $j$ 个任务后，要等待 $s$ 秒，则后续费用一定会加上 $(sumc[n]−sumc[j])×s$ ，于是可以提前加进去。换句话说，用图片表示出来两次的差别就是：

那么这时候的状态其实就已经不需要原来的 $j$ 的分段存在了，也就是说，状态少了一维，体现在复杂度上，就是复杂度从 $O(n^3)$ 退化到了 $O(n^2)$ 。

转移式子的话，就变成了（变量都还是原来的意思）：
$$
dp[i] = \min_{0\le k\lt i} dp[k] + sumt[i] \times (sumc[i] - sumc[k]) + s\times(sumc[n] - sumc[k])
$$
这样就是可以 AC 第一个部分分的算法了。其实也没什么技术难度，代码也就不放了。

接下来我们要进一步优化，再一次缩减一维也就是 $O(n)$ 。这要怎么办？我们这时候就要使用斜率优化了。顾名思义就是我们需要把这个按照斜率优化。

我们首先把这个式子一步一步的分解开来：
$$
dp[i] = \min_{0\le k\lt i} dp[k] + sumt[i] \times sumc[i] - sumt[i] \times sumc[k] + s\times sumc[n] - s\times sumc[k]
$$
然后我们就把唯一的变量 $sumc[k]$ 的项提一下，也就是：
$$
dp[i] = \min_{0\le k\lt i} dp[k] - (s + sumt[i]) \times sumc[k] + sumt[i]\times sumt[i] + s\times sumc[n]
$$
这时候，就已经很明显了，这个 $\min$ 里面的东西，一眼丁真就是一次函数啊。你看看这个 $s+sumt[i]$ 就是斜率吧，这个 $sumc[k]$ 作为变量是不是可以看作是 $x$ ，然后这个剩下的依托玩意就是 $b$ 了。

那么这样的一个东西我们拿到手上有什么用呢？

我们简单的考虑一下，这样的话，我们已经知道了这个一次函数的表达式，那么当前这个决策的坐标我们就知道了，也就是分别以 $sumc[k]$ 为 $x$ 轴，$dp[k]$ 为 $y$ 轴的坐标系上。而这个截距 $b$ 除了 $dp[k]$ 都是常量，我们可以直接算出来，并且第二档数据范围说过这个所有的 $t_i$ 和 $c_i$ 非负，也就是说，这个 $b$ 越大，当前的这个 $dp[k]$ 越大。

我们把上面这样可以更新 $dp[i]$ 的点 $k$ 称为决策点。

那么我们接下来要计算的东西就是，怎么样的节点算作最优呢？我们不妨设置两个点 $j, k$ 作为点 $i$ 的决策点，并且规定 $k\lt j \lt i$ 。

由于我们已经发现，截距 $b$ 越大，这个 $dp$ 值也越大，也就是说这样的单调性我嫩完全可以用单调队列维护。所以说，我们只需要维护一个单调队列，不断地记录斜率 $sumc[k]+s$ 的最小值即可。

那么接下来，就是重头戏了，第三档部分分，我们的 $t_i , c_i$ 非负性质被吃了，接下来该如何去做呢？

不难想到，我们要的决策点一定还是一样的，满足后面小于我，前面大于我，我们直接做二分即可，数据改用单调栈来维护单调上升。

代码也好写了。

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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
// #pragma GCC optimize(2)
// #pragma GCC optimize(3, "Ofast", "inline")
#include<bits/stdc++.h>
using namespace std;

#define int long long 

typedef long long ll;
typedef __int128 int128;

namespace FastIO 
{
    // char buf[1 << 20], *p1, *p2;
    // #define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++)
    template<typename T> inline T read(T& x) {
        x = 0;
        int f = 1;
        char ch;
        while (!isdigit(ch = getchar())) if (ch == '-') f = -1;
        while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
        x *= f;
        return x;
    }
    template<typename T, typename... Args> inline void read(T& x, Args &...x_) {
        read(x);
        read(x_...);
        return;
    }
    inline ll read() {
        ll x;
        read(x);
        return x;
    }
};
using namespace FastIO;

const int N = 3e5 + 10;

template<typename T, unsigned int N, bool (*func)(T, T)>
class MQueue {
private :
    pair<T , int >q[N];
    int hd, tl, len;
public :
    inline void clear(int len) { this->len = len; hd = 0, tl = -1; }
    inline int size() { return tl - hd + 1; }
    inline bool empty() { return hd > tl; }
    inline void push(pair<T, int> ele) {
        while(!empty() && (*func)(ele.first, q[tl].first)) tl--;
        q[++tl] = ele;
        while(!empty() && q[hd].second <= ele.second - len) hd++;
    }
    inline T front() { return q[hd].first; }
};

int n, s;
ll t[N], c[N];

ll dp[N];
ll q[N], hd, tl;

inline void Input() {
    read(n, s);
    for(int i = 1; i <= n; i++) {
        read(t[i], c[i]);
        t[i] += t[i - 1], c[i] += c[i - 1];
        dp[i] = 1e18;
    }
}

int Get(ll x) {
    int l = hd, r = tl - 1, best = tl;
    while(l <= r) {
        int mid = l + r >> 1;
        if(
            (dp[q[mid + 1]] - c[q[mid + 1]] * s - dp[q[mid]] + c[q[mid]] * s) >
            x * (c[q[mid + 1]] - c[q[mid]])
        ) {
            best = mid;
            r = mid - 1;
        } else l = mid + 1;
    }
    return q[best];
}

inline void Work() {
    q[0] = 0, hd = tl = 0;
    dp[0] = 0;
    for(int i = 1; i <= n; i++) {
		int j = Get(t[i]);
		dp[i] = dp[j] + t[i] * (c[i] - c[j]) + s * (c[n] - c[j]);
		while(
                hd < tl && 
                (dp[q[tl]] - c[q[tl]] * s - dp[q[tl - 1]] + c[q[tl - 1]] * s) * 
                (c[i] - c[q[tl]])
                >= (dp[i] - c[i] * s - dp[q[tl]] + c[q[tl]] * s) * 
                (c[q[tl]] - c[q[tl - 1]])
            ) tl--;
		q[++tl]=i;
    }
    printf("%lld\n", dp[n]);
}

signed main() {
    int T = 1;
    while(T--) {
        Input();
        Work();
    }
    return 0;
}

例题总结：附赠的下酒菜

这时候我们可以适当的讲一些玄学的知识了，我们不难发现，本道题目如果抽象一下，把斜率以一次函数的形式画出来，我们将会得到一个半凸包，具体点是下凸壳。

这时候，其实不难想到，斜率优化DP 就是一个在凸包上面维护一个值的过程。我们要求的决策点，有一些会破坏凸包的结构，也就是说，那些点都是不能要的。

而维护这样一个单调上升或下降的数据，我们可以用单调队列，单调栈以及我不会的李超线段树等等等等，这也是斜率优化DP的活性所在。

算法实战：最烈特调

查看相关标签喵！