CF1077F2 Pictures with Kittens (hard version)(单调队列+dp优化)

本文主要是介绍CF1077F2 Pictures with Kittens (hard version)(单调队列+dp优化)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目传送门

唉，曾经觉得单调队列学的没啥用。。。
在这里插入图片描述

题目大意

这个题目的意思就是说：
给你一个数列a，你需要选择s个元素，使得连续的k个元素都至少有一个被选中。
需要你最大化选出来的所有数的和。
也就是滑动窗口问题：一个k单位大小的窗口，每一个窗口必须有数字选中，求最大和。

思路

这道题我也没有思路。。还看题解聚聚们的做法：
这就是用单调队列，先模拟一下滑动窗口.
这里参考一下大佬的博客，我觉得非常清楚易懂！
大佬博客传送门
在这里插入图片描述

至此，我想解释一下为什么在单调队列搞掉队尾元素的情况下，为什么要用dp数组来确定？
那是因为，我们这道题单调队列里面，存的其实是dp[][j-1]而不是a[]，（比你小还比你强，你就要被淘汰呜呜呜）
还有一点就是dp[i][j]这个dp数组其实应该是从前i个元素中选取j个元素，其中保证a[i]一定被选中。

#include<iostream>
using namespace std;
typedef long long ll;
ll dp[5050][5005];
int q[2102100];
ll a[2100210];
int main(){int n,k,s;cin>>n>>k>>s;for(int i=1;i<=n;i++)cin>>a[i];//dp[a][b]代表的是选了第a个数（包括第a个数）恰好选了b个数字的最大值for(int i=0;i<=n;i++){for(int j=0;j<=s;j++)dp[i][j]=-1111111111111111;}dp[0][0]=0;for(int j=1;j<=s;j++){int l=0,r=1;q[0]=0;for(int i=1;i<=n;i++){while(l<r&&q[l]<i-k)l++;dp[i][j]=dp[q[l]][j-1]+a[i];///**/printf("dp[ %d ][ %d ] = %lld,l = %d, r = %d\n",i,j,dp[i][j],q[l],q[r]);while(l<r&&dp[q[r-1]][j-1]<dp[i][j-1])r--;q[r++]=i;}cout<<endl;} ll maxx=-1111111111111111;for(int i=n-k+1;i<=n;i++){//	cout<<dp[i][s]<<endl;maxx=max(maxx,dp[i][s]);}if(maxx<0){cout<<"-1"<<endl;return 0;}cout<<maxx<<endl;return 0;
}