洛谷P1725--琪露诺(单调队列)

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

https://www.luogu.org/problemnew/show/P1725

关于滑动窗口的解释https://www.cnblogs.com/albert67/p/10449039.html

dp[i]=max(dp[i-k])l<=k<=r+a[i]

#include<iostream>
#include<deque>
#include<algorithm>
using namespace std;
int a[],dp[];
struct Node{
int v,num;
};
deque<Node> q;
int main(){
int n,l,r;
cin>>n>>l>>r;
for(int i=;i<=n;i++)
cin>>a[i];
int p=;
struct Node tmp;
for(int i=l;i<=n;i++){
while(!q.empty()&&q.back().v<dp[p])
q.pop_back();
tmp.num=p;tmp.v=dp[p];
q.push_back(tmp);
while(!q.empty()&&q.front().num+(r-l+)<=p)
q.pop_front();
dp[i]=q.front().v+a[i];
p++;
}
cout<<*max_element(dp+n-r+,dp+n)<<endl;
return ;
}