本文主要是介绍Codeforces Round #521 (Div. 3) F2(单调队列优化DP)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：
给出n个数，让从中选择x个数，使得从n个数中所有大小为k的区间里都会至少有一个数选在x中，再此条件下求出x数和的最大值。
思路
看到任意大小为k的区间至少有一个数，让我想到之前学的单调队列入门 中那道烽火传递那道题也有连续一个区间至少选一个的约束条件，所以可以写出类似的状态转移方程：
d ( i , j ) = m a x { d ( s , j − 1 ) } + a [ i ] ( i − k < = s < i ) 其 中 d ( i , j ) 代 表 的 是 前 i 个 选 j 个 和 最 大 的 值 d(i, j) = max\{d(s, j-1)\} + a[i] (i-k<=s <i)\\ 其中d(i, j)代表的是前i个选j个和最大的值 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;
}
这篇关于Codeforces Round #521 (Div. 3) F2(单调队列优化DP)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
