Codeforces 1077F2 Pictures with Kittens (hard version)（DP+单调队列优化）

题目链接：Pictures with Kittens (hard version)

题意：给定n长度的数字序列ai，求从中选出x个满足任意k长度区间都至少有一个被选到的最大和。

题解：数据量5000，O（n^3）的DP不适用。需要加个单调队列优化。

注意每次是从$[i-k,i)$区间，选择加上ai。每次清空双向队列。

 #include <queue>

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 typedef long long ll;

 const int N=+;

 ll a[N],dp[N][N],ans=-1e18;

 deque <int> q;

 int main(){

     int n,k,x;

     scanf("%d%d%d",&n,&k,&x);

     for(int i=;i<=n;i++) scanf("%lld",&a[i]);

     for(int i=;i<=n;i++)

     for(int j=;j<=n;j++)

     dp[i][j]=-1e18;

     dp[][]=;

     for(int j=;j<=x;j++){

         q.push_back();

         for(int i=;i<=n;i++){

             while(!q.empty()&&q.front()<i-k) q.pop_front();

             dp[i][j]=dp[q.front()][j-]+a[i];

             while(!q.empty()&&dp[q.back()][j-]<=dp[i][j-]) q.pop_back();

             q.push_back(i);

         }

         q.clear();

     }

     for(int i=n-k+;i<=n;i++) ans=max(ans,dp[i][x]);

     if(ans<) ans=-;

     printf("%lld\n",ans);

     return ;

 }