洛谷P1725 琪露诺（单调队列+dp）
传送门
设 d [ i ] d[i] d[i]表示跳到位置 i i i的最小值，那么不难想到状态转移方程为：
d [ i ] = m a x { d [ i − j ] } + a [ i ] , i − r ≤ j ≤ i − l d[i]=max\{d[i-j]\}+a[i],i-r\leq j \leq i-l d[i]=max{d[i−j]}+a[i],i−r≤j≤i−l
本题可以写填表法，但是显然刷表法（由当前状态更新未来状态）更好。因为区间 [ i − r , i − l ] [i-r,i-l] [i−r,i−l]长度是固定的，那么我们可以使用单调队列 O ( 1 ) O(1) O(1)取得最值，这时来了一个问题，对于点 i i i，我们需要更新 [ i + l , i + r ] [i+l,i+r] [i+l,i+r]的dp值吗？这样的话时间复杂度就到了 O ( n 2 ) O(n^2) O(n2)了
实际上我们求出之前每个长度为 l − r + 1 l-r+1 l−r+1的区间的最值后，显然在这个区间我们只需对每个数更新 d [ i + l ] d[i+l] d[i+l]即可，因为 l + r = r + l l+r=r+l l+r=r+l
开始对 d d d数组初始化为 − i n f -inf −inf，设置 d [ 0 ] = 0 d[0]=0 d[0]=0代表只能从这个状态转移而来。最后对 [ n + 1 , n + l ] [n+1,n+l] [n+1,n+l]范围内取答案即可
#include <bits/stdc++.h>
#include <unordered_map>
#include <unordered_set>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ins insert
#define Vector Point
#define lowbit(x) (x&(-x))
#define mkp(x,y) make_pair(x,y)
#define mem(a,x) memset(a,x,sizeof a);
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
const double eps=1e-8;
const double pi=acos(-1.0);
const int inf=0x3f3f3f3f;
const double dinf=1e300;
const ll INF=1e18;
const int Mod=1e9+7;
const int maxn=2e5+10;
int a[maxn],q[maxn],d[maxn*2];
int n,l,r;
int main(){
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>l>>r;
memset(d,0x8f,sizeof d);
d[0]=0;
for(int i=0;i<=n;i++) cin>>a[i];
int h=0,t=0,m=r-l+1;
for(int i=0;i<=n;i++){
while(h<t && i-q[h]+1>m) h++;
while(h<t && d[i]>d[q[t-1]]) t--;
q[t++]=i;
d[i+l]=a[i+l]+d[q[h]];
}
int ans=-inf;
for(int i=n+1;i<=n+l;i++)
ans=max(ans,d[i]);
cout<<ans<<endl;
return 0;
}