斜率优化 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) ]

斜率具有单调性，使用单调队列优化即可。

代码

#include <bits/stdc++.h> #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++) #define rpl(x, a, b) for (auto x = a; x < b; x++) #define per(x, a, b) for (auto x = a; x >= b; x--)  using namespace std;  #define pii pair<int, int> #define x first #define y second  const int N = 5e4 + 10; int n, m, a[N], b[N], s[N], dp[N]; deque<int> 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[i]; 	rep(i, 2, n) s[i] += s[i - 1]; 	rep(i, 1, n) a[i] = s[i] + i;    	 	q.push_back(0); 	rep(i, 1, n) { 		while (q.size() > 1 && slope(q[0], q[1]) <= 2 * (a[i] - m)) q.pop_front();		 		dp[i] = dp[q[0]] + (a[i] - a[q[0]] - m) * (a[i] - a[q[0]] - m);		 		while (q.size() > 1 && slope(q[q.size() - 2], q.back()) > slope(i, q.back())) q.pop_back(); 		 		q.push_back(i); 	} 	 	cout << dp[n] << endl; 	return 0; }