例题：薯片
小明现在体重 \(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;
}