单调队列dp求助
查看原帖
单调队列dp求助
490978
小超手123楼主2022/8/31 15:57
#include<bits/stdc++.h>
using namespace std;
int n,l,r,ans=-1e9,a[300005],f[300005]; //f[i]表示跳到i 
int que[300005],head=1,tail=0; //head~tail
int main() {
	scanf("%d %d %d",&n,&l,&r);
	for(int i=0;i<=n;i++){
		scanf("%d",&a[i]);
		f[i]=-1e9;
	}
	f[0]=0;
	for(int i=0;i<l;i++)
	for(int i=0;i<=n;i++){
		//单调队列求最大值(i-r~i-l) 
		while(tail>=head&&i-que[head]+1>r-l+1)head++; //过期的
		while(tail>=head&&f[que[tail]]<f[i-l+1]&&i>=l)tail--;
		que[++tail]=i-l+1;
		f[i]=f[que[tail]]+a[i];
		/*for(int j=i-r;j<=i-l;j++){  //j->i
			if(j>=0)
			    f[i]=max(f[i],f[j]+a[i]);
		}*/
		if(i>=n-r+1)
		    ans=max(ans,f[i]);
	}
	cout<<ans;
	return 0;   
}

2022/8/31 15:57
加载中...