# ConanKIDの小窝

### 单调队列优化DP学习笔记

posted on 2021-08-20 10:07:16 | under 学习笔记 |

$$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)\}$$

$$dp_{i,1}=\max\limits_{i-k\le j\le i-1}\{dp_{j,0}-sum_j\}+sum_i$$

#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;
}

$$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\}$$

#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;
}

$$dp_i=\max\limits_{x_i-d-x\le x_j\le x_i-d+x}\{dp_j\}+s_i$$

#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)\}$$