斜率优化DP学习笔记

~~我是个DP菜鸡实锤了~~ --- 先来看[题](https://vjudge.net/problem/HDU-3507) 考虑DP，应该很容易可以得出状态转移方程。设 $dp_i$ 表示前 $i$ 个单词进行分组的代价，显然 $$dp_i=\min\limits_{0\le j<i }\{dp_j+(sum_i-sum_j)^2+m\}$$ 其中 $sum$ 表示前缀和。 但是朴素计算这个东西的复杂度是 $O(n^2)$ 的，我们无法承受。因此必须优化。枚举 $dp_{1-n}$ 的循环显然是不可少的，因此只能在计算状态转移方程上做文章。 若 $j<k$，考虑决策 $k$ 比决策 $j$ 更优的条件： $$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$$ 将含 $sum_i$ 的项移到一边去 $$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}$$ 这个式子的右边就长得很像斜率了。 而我们发现 $sum_i$ 是单调递增的。也就是说，如果对于状态 $i$，决策 $k$ 优于 $j$，那么随着 $sum_i$ 的增大，上述式子一定始终成立。这样的话，我们在之后的计算过程中，就完全可以不考虑 $j$ 这个“废点”。 因此，我们可以维护一个单调队列，保存所有合法的决策点。在整个过程中，一旦遇到队头两点 $j,k$ 组成的“斜率”——也就是上面式子的右边——小于等于 $2sum_i$，就可以直接把点$j$从队列里给`pop`掉（因为它将永远不会优于点 $k$）。同时，我们每枚举到一个状态 $i$，就要将点 $i$ 入队，同时维护队内相邻两点的斜率的单调性（这也是为了及时排除无用决策，原理同上）。 这样一来，每个点至多入队和出队一次，我们就做到了 $O(n)$ 的复杂度。 ```cpp #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; } ``` 把分子和分母单独写一个函数应该会比较清楚吧。 --- 再来看[这个](https://www.luogu.com.cn/problem/P3195) 考虑朴素DP： $$dp_i=\min\limits_{0\le j<i}\{dp_j+(sum_i-sum_j+i-j-1-L)^2\}$$ 发现这个式子比较臃肿，可以换个元。设 $h_i=sum_i+i$，$g_i=sum_i+i-1-L$。于是可以改写为 $$dp_i=\min\limits_{0\le j<i}\{dp_j+(g_i-h_j)^2\}$$ 接下来就是一样的套路。考虑若 $j<k$，决策 $k$ 优于 $j$ 的条件： $$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}$$ 由于 $g_i$ 也是单调递增的，所以也可以维护一个斜率递增的单调队列，然后及时排除无用决策。复杂度 $O(n)$。这题代码和上面几乎一模一样，就不给了。 --- Q：何时可以考虑斜率优化DP？ A：状态转移方程遵循如下形式： $$dp_i=\min\{dp_j+val(i,j)\}$$ 其中 $val$ 是一个与 $i,j$ **均有关**的多项式（一般和前缀和有关，这样才能利用单调性进行决策点的维护）。这个时候就可以推一推式子，再利用决策单调性进行优化了。 --- [一道经典题](https://www.luogu.com.cn/problem/P5017) 这道题挺有意思的，做法很多。设第 $i$ 个人坐上车的时间为 $time_i$，那么答案就是 $\sum(time_i-t_i)$，即 $\sum time_i-\sum t_i$。发现后面那个 $\sum t_i$ 是固定的，所以只需要让前面的部分最小即可。 设 $dp_i$ 表示接送完前$i$分钟的所有学生所需的最小代价，易得状态转移方程： $$dp_i=\min\limits_{0\le j\le i-m}\{dp_j+i(sum_i-sum_j)\}$$ 其中 $sum_i$ 表示前 $i$ 分钟来等车的总人数。 我们发现 $i(sum_i-sum_j)$ 是一个与 $i,j$ 均有关的多项式，因此显然是可以推一推式子然后斜率优化的。式子这里就不推了，很套路。 代码稍有不同。 ```cpp #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; } ``` --- 几道练习题： - [P2365 任务安排](https://www.luogu.com.cn/problem/P2365) - [P3628 [APIO2010]特别行动队](https://www.luogu.com.cn/problem/P3628) - [P3648 [APIO2014]序列分割](https://www.luogu.com.cn/problem/P3648) - [P4072 [SDOI2016]征途](https://www.luogu.com.cn/problem/P4072) --- ~~没了~~