# ConanKIDの小窝

### 斜率优化DP学习笔记

posted on 2021-08-16 21:46:04 | under 学习笔记 |

$$dp_i=\min\limits_{0\le j<i }\{dp_j+(sum_i-sum_j)^2+m\}$$

$$dp_j+(sum_i-sum_j)^2+m\ge dp_k+(sum_i-sum_k)^2+m$$

$$dp_j+sum^2_i+sum^2_j-2sum_isum_j+m\ge dp_k+sum^2_i+sum^2_k-2sum_isum_k+m$$

$$dp_j+sum^2_j-2sum_isum_j\ge dp_k+sum^2_k-2sum_isum_k$$

$$2sum_i(sum_k-sum_j)\ge dp_k+sum^2_k-dp_j-sum^2_j$$

$$2sum_i\ge\dfrac{dp_k+sum^2_k-dp_j-sum^2_j}{sum_k-sum_j}$$

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n, m;
int a[500005];
int sum[500005], dp[500005];
int q[500005];
int up(int x, int y) {return dp[y] + sum[y] * sum[y] - dp[x] - sum[x] * sum[x];}//点x和点y组成的斜率的分子
int down(int x, int y) {return sum[y] - sum[x];}//同上，分母
void work() {
memset(dp, 0, sizeof(dp)); memset(q, 0, sizeof(q)); memset(sum, 0, sizeof(sum));
for (int i = 1; i <= n; i++)
cin >> a[i], sum[i] = sum[i - 1] + a[i];
int l = 1, r = 1; q[1] = 0;
for (int i = 1; i <= n; i++) {
while(l + 1 <= r && up(q[l], q[l + 1]) <= 2 * sum[i] * down(q[l], q[l + 1])) l++;//一旦发现推的式子成立，就排除队头决策
int j = q[l];
dp[i] = dp[j] + (sum[i] - sum[j]) * (sum[i] - sum[j]) + m;//这时可以直接取出队头计算了，由于队内斜率的单调性，q[l]一定最优
while (l + 1 <= r && up(q[r - 1], q[r]) * down(q[r], i) >= up(q[r], i) * down(q[r - 1], q[r])) r--;//维护决策单调性
q[++r] = i;//把i入队
}
cout << dp[n] << endl;
}
signed main() {
while (cin >> n >> m)
work();
return 0;
}

$$dp_i=\min\limits_{0\le j<i}\{dp_j+(sum_i-sum_j+i-j-1-L)^2\}$$

$$dp_i=\min\limits_{0\le j<i}\{dp_j+(g_i-h_j)^2\}$$

$$dp_j+(g_i-h_j)^2\ge dp_k+(g_i-h_k)^2$$

$$dp_j+h^2_j-2g_ih_j\ge dp_k+h^2_k-2g_ih_k$$

$$2g_i(h_k-h_j)\ge dp_k+h^2_k-dp_j-h^2_j$$

$$2g_i\ge \dfrac{dp_k+h^2_k-dp_j-h^2_j}{h_k-h_j}$$

Q：何时可以考虑斜率优化DP？

A：状态转移方程遵循如下形式：

$$dp_i=\min\{dp_j+val(i,j)\}$$

$$dp_i=\min\limits_{0\le j\le i-m}\{dp_j+i(sum_i-sum_j)\}$$

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n, m, maxt;
int a[505];
int sum[4000005];
int dp[4000005];
int q[4000005];
int ans = 1e18;
int up(int x, int y) {return dp[y] - dp[x];}
int down(int x, int y) {return sum[y] - sum[x];}
signed main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> a[i];
sum[++a[i]]++; maxt = max(maxt, a[i]);
}
for (int i = 1; i <= maxt + m; i++)
sum[i] += sum[i - 1];
int l = 1, r = 1; q[1] = 0;
for (int i = 1; i <= maxt + m; i++) {
if (i > m) {
int x = i - m;
while (l + 1 <= r && up(q[r - 1], q[r]) * down(q[r], x) >= up(q[r], x) * down(q[r - 1], q[r])) r--;
q[++r] = x;
}//由于此时i-m也是决策的一个候选项，所以先将i-m入队
while (l + 1 <= r && up(q[l], q[l + 1]) <= i * down(q[l],q[l + 1])) l++;
int j = q[l];
dp[i] = dp[j] + (sum[i] - sum[j]) * i;
if (i >= maxt) ans = min(ans, dp[i]);//注意答案要取最小值
}
for (int i = 1; i <= n; i++)
ans -= a[i];
cout << ans << endl;
return 0;
}