斜率优化 DP 解析（[HNOI2008] 玩具装箱 题解）

前置知识：单调队列（一般情况下）、一次函数、前缀和（例题）。
关于

斜率优化一般解决这样的问题：

\[dp_i = \min \{ dp_j + f(i, j) \}\]
当然这种也算：

\[dp_i = \max \{ dp_j + f(i, j) \}\]
例题

链接是这个：跳转到洛谷。
题目大意：将一段数组分段，每段的代价是 \((j - i + \sum_{k=i}^j{c_k} - L) ^2\)，求分段代价合的最小值。
第一次变形

令前缀和数组为 \(s\)，即：\(s_i = \sum_1^i{c_k}\)，则：\(\sum_{k=i}^j{c_k} = sum_j - sum_{i - 1}\)。
令：\(m = L + 1\)。
则：\(dp_i = \min \{ dp_j + (i - j + s_i - s_j +m) \}\)。
继续令：\(a_i = i + s_i\)。
则：\(dp_i = \min \{ dp_j + (a_i - a_j - m)^2 \}\)。
就是上面关于所提到的类似的式子。
弱版的话直接这样暴力 DP \(O(n^2)\) 就能过。
第二次变形

解决：\(dp_i = \min \{ dp_j + (a_i - a_j - m)^2 \}\) 的问题。
假设存在更优解 \(j\) 且 \(j\) 小于当前最优值 \(k\)，即：\(j < k\).
那么很容易得到：\(dp_j + (a_i - a_j - m)^2 \le dp_k + (a_i - a_k - m)^2\)。
化解移项（过程略）后得到的结果：

\[(dp_j + a_j ^ 2) - (dp_k - a_k^2) \le 2(a_i - m)(a_j - k)\]
令：\(f(i) = dp_i + a_i^2\)，可得：

\[\frac{f(j) - f(k)}{a_j - a_k} \le 2(a_i - m)\]
斜率具有单调性，使用单调队列优化即可。
代码

[code]#include #define GCC optimize("Ofast", "-funroll-all-loops")#pragma GCC target("popcnt")#define int long long#define rep(x, a, b) for (auto x = a; x = b; x--)using namespace std;#define pii pair#define x first#define y secondconst int N = 5e4 + 10;int n, m, a[N], b[N], s[N], dp[N];deque q;int f(int x) { return dp[x] + a[x] * a[x]; }double slope(int x, int y) { return (double)(f(x) - f(y)) / (a[x] - a[y]); }signed main(){        ios::sync_with_stdio(false);         cin.tie(nullptr);         cin >> n >> m;        m ++;                rep(i, 1, n) cin >> s;        rep(i, 2, n) s += s[i - 1];        rep(i, 1, n) a = s + i;                   q.push_back(0);        rep(i, 1, n) {                while (q.size() > 1 && slope(q[0], q[1])  1 && slope(q[q.size() - 2], q.back()) > slope(i, q.back())) q.pop_back();                                q.push_back(i);        }                cout