滑动窗口+动态规划

前言：这个题目不能用简单的动态规划来做，那么怎么用滑动规划来维护前面 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;
}