老师牌题解用单调队列优化DP

#include<bits/stdc++.h>
using namespace std;
struct node{
int val,id;
};
int main(){
int n,l,r;
cin>>n>>l>>r;
vector<int>vec(n+1),dp(n+1,INT_MIN);
for(int i=0;i<=n;i++) cin>>vec[i];
dp[0]=0;
deque<node>Q;
int p=0;
for(int i=l;i<=n;i++){
while(Q.size()){
if(dp[p]>Q.back().val) Q.pop_back();
else break;
}
Q.push_back({dp[p],p});
while(Q.front().id<i-r) Q.pop_front();
dp[i]=Q.front().val+vec[i];
p++;
}
int ans=INT_MIN;
for(int i=n-r+1;i<=n;i++){
ans=max(ans,dp[i]);
}
cout<<ans<<endl;
}