斜率优化学习笔记
Published:
例题：薯片
小明现在体重 $W$ 公斤，减肥将会持续 $n$ 天。第 $i$ 天如果不吃薯片体重将会减少 $A$ 公斤，吃了体重会增加 $D_i$ 公斤。但是不吃薯片实在是很难受，这个难受情况用压力值来描述。一开始压力值为 $0$，每一天不吃薯片压力值将会增加 $1$，吃了薯片压力值又会变回 $0$。每天结束的时候，小明的体重会增加 $B \times 压力值$。注意，小明有神奇的能力，体重可以是负的。小明想知道，$n$ 天后他最多可以瘦到多少公斤？
要求时间复杂度 $O(n)$。
朴素的 DP！
设 $f_i$ 为第 $i$ 天吃了薯片的体重最小值（最终答案为 $f_{n+1}$）。有：
\[f_i = \begin{cases} W & i = 0 \\ D_i + \min\limits_{j=0}^{i-1} \left(f_{i-j-1} - A \times j + B \times \frac {j \times (j+1)} 2\right) & \text{otherwise} \\ \end{cases}\]时间复杂度 $O(n^2)$。
斜率优化的预备：重新整理转移式
\[\begin{aligned} f_i &= D_i + \min\limits_{j=0}^{i-1} \left(f_{i-j-1} - A \times j + B \times \frac {j \times (j+1)} 2\right) \\ f_i &= D_i + \min\limits_{j=0}^{i-1} \left(f_j - A \times (i-j-1) + B \times \frac {(i-j-1) \times (i-j)} 2\right) & j \gets i-j-1 \\ \end{aligned}\] \[f_i - \left(D_i - A \times (i-1) + B \times \frac {i \times (i-1)} 2\right) = \min\limits_{j=0}^{i-1} \left(\left(f_j + A \times j + B \times \frac {j \times (j+1)} 2\right) - B \times i \times j\right)\]令 $P(i) = D_i - A \times (i-1) + B \times \frac {i \times (i-1)} 2$，$Q(j) = f_j + A \times j + B \times \frac {j \times (j+1)} 2$。则：
\[f_i - P(i) = \min\limits_{j=0}^{i-1} (Q(j) - B \times i \times j)\]斜率优化！
众所周知，直线的解析式为 $y = kx + b$。可以写为 $b = y - kx$。
不妨把动态规划柿子中的 $f_i - P(i)$ 看作 $b$，$Q(j)$ 看作 $y$，$B \times i$ 看作 $k$，$j$ 看作 $x$。
问题转化为：在已有的 $i$ 个 $(j,Q(j))$ 的点中，找一个点 $p$，作一条斜率为 $k$ 的直线，求最小的截距。
因此，$p$ 必定在已有的 $i$ 个点的下凸壳上。
注意到 $k$ 单调不降，使用单调队列进行维护。
#include <bits/stdc++.h>
#define rep(i, l, r) for (ll i = (l); i <= (r); i++)
#define per(i, r, l) for (ll i = (r); i >= (l); i--)
using namespace std;
typedef long long ll;
struct Point {
ll x, y;
Point(ll x = 0, ll y = 0) : x(x), y(y) {}
};
long double slope(Point &A, Point &B) {
return (long double)(B.y - A.y) / (B.x - A.x);
}
const int MAXN = 3e5;
const ll INF = 1e18;
ll n, A, B, W;
ll D[MAXN];
ll f[MAXN];
ll P(ll x) {
return x * (x - 1) / 2 * B - A * x + A + D[x];
}
ll Q(ll x) {
return f[x] + x * (x + 1) / 2 * B + A * x;
}
int main() { ios::sync_with_stdio(0); cin.tie(0);
freopen("chips.in", "r", stdin);
freopen("chips.out", "w", stdout);
cin >> n >> A >> B >> W;
rep(i, 1, n)
cin >> D[i];
deque<Point> dq;
f[0] = W;
dq.push_back(Point(0, Q(0)));
rep(i, 1, n+1) {
ll k = B * i;
while (int(dq.size()) >= 2 && slope(dq[0], dq[1]) < k)
dq.pop_front();
auto [x, y] = dq.front();
f[i] = y - k * x;
f[i] += P(i);
auto p = Point(i, Q(i));
while (int(dq.size()) >= 2 && (slope(dq[dq.size()-2], dq.back()) >= slope(dq.back(), p)))
dq.pop_back();
dq.push_back(p);
}
cout << f[n+1] << '\n';
return 0;
}