前言:这个题目不能用简单的动态规划来做,那么怎么用滑动规划来维护前面 l 到 r 区间最大值呢,我们每次送到下标 i - l 的元素送到大顶堆中,每次把不符合下标的元素弹出
题目地址
#include<bits/stdc++.h>
#include<iostream>
using namespace std;
#define int long long
const int N = (int)5e5+10;
int n,l,r;
int a[N];
int vis[N];
signed main(){
cin >> n >> l >> r;
int ans = -0x3f3f3f3f3f3f;
for(int i=0;i<=n;i++) cin >> a[i];
priority_queue<pair<int,int>> q;
for(int i=1;i<l;i++) {
a[i] = 0; vis[i] = 1;
}
q.push({0,0});
for(int i=l+1;i<=(n+l);i++){
if(vis[i-l]==0) q.push({a[i-l],i-l});
while(q.size() && q.top().second<(i-r)){
q.pop();
}
if(q.empty()){
a[i] = 0; vis[i] = 1;
continue;
}
a[i] += q.top().first;
if(i>n){
ans = max(ans,a[i]);
}
}
cout << ans;
return 0;
}