单调队列优化DP学习笔记
Tarantula
2021-08-20 10:07:16
先来看[题](https://www.luogu.com.cn/problem/P2034)
考虑DP。设$dp_{i,0/1}$表示第$i$个数选或不选时，前$i$个数的最大结果。显然有状态转移方程：
$$dp_{i,0}=\max\{dp_{i-1,0},dp_{i-1,1}\}$$
$$dp_{i,1}=\max\limits_{i-k\le j\le i-1}\{dp_{j,0}+(sum_i-sum_j)\}$$
其中$sum$表示前缀和。
但是朴素计算的复杂度是$O(n^2)$的，因此必须优化。
将状态转移方程变形：
$$dp_{i,1}=\max\limits_{i-k\le j\le i-1}\{dp_{j,0}-sum_j\}+sum_i$$
我们发现，当$i$增加$1$时，$j$的取值的上界和下界均会增加$1$。这个形式就长得很像滑动窗口了。
因此，我们可以用一个单调队列，维护$dp_{j,0}-sum_j$的最大值。这样一来，总时间复杂度就是维护单调队列的复杂度，即$O(n)$。
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n, k;
int a[100005], sum[100005];
int dp[100005][2], q[100005];
int l, r;
int calc(int x) {return dp[x][0] - sum[x];}
signed main() {
cin >> n >> k;
for (int i = 1; i <= n; i++)
cin >> a[i], sum[i] = sum[i - 1] + a[i];
l = r = 1; q[1] = 0;
for (int i = 1; i <= n; i++) {
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);
while (l <= r && i - q[l] > k) l++;//排除队头“过期”的决策
dp[i][1] = calc(q[l]) + sum[i];//直接取出队头计算
while (l <= r && calc(i) >= calc(q[r])) r--;//维护单调性
q[++r] = i;
}
cout << max(dp[n][0], dp[n][1]) << endl;
return 0;
}
```
---
再来看[这个](https://vjudge.net/problem/POJ-1821)
设$dp_{i,j}$表示前$i$个人刷前$j$块木板所能得到的最大价值。那么显然：
$$dp_{i,j}=\max\limits_{j-l_i\le k\le s_i-1}\{dp_{i-1,k}+p_i\times(j-k)\}$$
变形得
$$dp_{i,j}=p_i\times j+\max\limits_{j-l_i\le k\le s_i-1}\{dp_{i-1,k}-p_i\times k\}$$
我们把外层循环的$i$看做定值，那么随着$j$的增大，$k$的上界不变，下界增大。因此，我们也可以按照上题的方法，维护一个$dp_{i-1,k}-p_i\times k$单调递减的队列，从而将时间复杂度优化至$O(nm)$。
```cpp
#include<iostream>
#include<algorithm>
using namespace std;
int n, m;
struct node {
int p, l, s;
bool operator < (const node &a) const {return s < a.s;}
} a[100005];//首先要把所有人按照s排序
int dp[105][100005], q[100005];
int l, r;
int calc(int i, int k) {return dp[i - 1][k] - a[i].p * k;}
int main() {
cin >> n >> m;
for (int i = 1; i <= m; i++)
cin >> a[i].l >> a[i].p >> a[i].s;
sort(a + 1, a + 1 + m);
for (int i = 1; i <= m; i++) {
l = 1, r = 0;//每次新建一个队列
for (int k = max(0, a[i].s - a[i].l); k <= a[i].s - 1; k++) {
while (l <= r && calc(i, q[r]) <= calc(i, k)) r--;
q[++r] = k;
}//将所有可能的决策入队
for (int j = 1; j <= n; j++) {
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);//第i个人可以什么都不刷，或第j块木板可以不刷
if (j >= a[i].s) {
while (l <= r && q[l] < j - a[i].l) l++;
if (l <= r) dp[i][j] = max(dp[i][j], calc(i, q[l]) + a[i].p * j);
}
}
}
cout << dp[m][n] << endl;
return 0;
}
```
---
[一道经典题](https://www.luogu.com.cn/problem/P3957)
很有意思的好题。考虑二分答案，问题转化为当跳跃距离为$[d-x,d+x]$时能取得多少分数。这个东西就可以DP了。
设$dp_i$表示前$i$个格子能取得的最大分数，那么显然：
$$dp_i=\max\limits_{x_i-d-x\le x_j\le x_i-d+x}\{dp_j\}+s_i$$
注意到$x_i$是单调递增的，所以这个东西显然也是可以单调队列优化的。时间复杂度$O(n)$。
```cpp
#include<bits/stdc++.h>
using namespace std;
int n, d, k;
int a[500005];
int s[500005];
int dp[500005];
int q[500005], l, r;
bool check(int x) {
dp[0] = 0;
for (int i = 1; i <= n; i++)
dp[i] = -1e9;
int p = 0; l = 1, r = 0;
for (int i = 1; i <= n; i++) {
while (a[i] - a[p] >= max(1, d - x) && p < i) {//把状态i的所有可能决策入队
if (dp[p] == -1e9) {p++; continue;}//p不可到达，则直接退出
while (l <= r && dp[q[r]] <= dp[p]) r--;
q[++r] = p++;//将p入队
}
while (l <= r && a[i] - a[q[l]] > d + x) l++;//排除队头“过期”决策
if (l <= r) dp[i] = dp[q[l]] + s[i];
if (dp[i] >= k) return 1;
}
return 0;
}
void work() {
int l = -1, r = 5000001;
while (l + 1 < r) {
int mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid;
}//二分
if (r != 5000001) cout << r << endl;
else cout << -1 << endl;
}
int main() {
cin >> n >> d >> k;
for (int i = 1; i <= n; i++)
cin >> a[i] >> s[i];
work();
return 0;
}
```
---
Q：何时可以考虑单调队列优化DP？
A：状态转移方程遵循如下形式：
$$dp_i=\max\{dp_j+val(i,j)\}$$
其中$val$是一个**仅与$i,j$中的一项有关**的多项式。如果含$i,j$的乘积项的话，那就考虑斜率优化吧。
---
几道练习：
- [P4954 [USACO09OPEN]Tower of Hay G](https://www.luogu.com.cn/problem/P4954) 比较有意思的变形
- [P3089 [USACO13NOV]Pogo-Cow S](https://www.luogu.com.cn/problem/P3089) 很奇特的题目
- [P1776 宝物筛选](https://www.luogu.com.cn/problem/P1776) 单调队列优化多重背包的板子
- [P2569 [SCOI2010]股票交易](https://www.luogu.com.cn/problem/P2569) 神题，细节比较多