Codeforces Round #521 (Div. 3) F2(单调队列优化DP)

本文主要是介绍Codeforces Round #521 (Div. 3) F2(单调队列优化DP)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：

给出n个数，让从中选择x个数，使得从n个数中所有大小为k的区间里都会至少有一个数选在x中，再此条件下求出x数和的最大值。

思路

看到任意大小为k的区间至少有一个数，让我想到之前学的单调队列入门中那道烽火传递那道题也有连续一个区间至少选一个的约束条件，所以可以写出类似的状态转移方程：
$d(i, j) = max\{d(s, j-1)\} + a[i] (i-k<=s <i)\\ 其中d(i, j)代表的是前i个选j个和最大的值$
然后我们用单调栈优化的就是从[i-k, i)这个区间中选择最大值的过程。
代码：

#include <bits/stdc++.h>
using namespace std;typedef long long ll;
const ll inf = 1e14;
const int maxn = 5010;
ll d[maxn][maxn];
ll a[maxn];
int qu[maxn];
int main()
{// freopen("/Users/maoxiangsun/MyRepertory/acm/i.txt", "r", stdin);int n,k,x;cin >> n >> k >> x;for(int i = 1; i <= n; i++) cin >> a[i];for(int i = 0; i <= n; i++) {for(int j = 0; j <= x; j++) {d[i][j] = -inf;}}d[0][0]=0;for(int j = 1; j <= x; j++) { int head = 1, tail = 0;   // 注意每次要清空for(int i = 1; i <= n; i++) {while(head <= tail && qu[head] < i - k) head++;while(head <= tail && d[i-1][j-1] > d[qu[tail]][j-1]) tail--;qu[++tail] = i-1;d[i][j] = d[qu[head]][j-1] + a[i];}}ll ans = -inf;for(int i = n - k + 1; i <= n; i++) {ans = max(ans, d[i][x]);}if(ans < 0) cout << -1 ;else cout << ans;return 0;
}