[网络协议]SSL P2884 假期【DP】【单调队列】

题目

思路

这道题的思路很巧妙
我们把 $i$ 作为终点，把 $i?l$ 作为起点加入队列，然后用队列维护最小的前缀和位置。

代码

#include<iostream>
#include<cstdio>
using namespace std;
long long q[1000010],a[1000010],b[1000010];
long long n,l,r,ans=-1e18;
int main()
{
	scanf("%lld%lld%lld",&n,&l,&r);
	for(long long i=1; i<=n; i++)
	   scanf("%lld",&a[i]);
	for(long long i=1; i<=n; i++)
	   b[i]=b[i-1]+a[i];
	long long hd=1,tl=0;
	for(long long i=1; i<=n; i++)
	 {
	 	while(hd<=tl&&q[hd]<i-r)
	 	  hd++;
	 	if(i>=l)
	 	 {
	 	 	while(hd<=tl&&b[q[tl]]>=b[i-l])
	 	 	  tl--;
	 	 	q[++tl]=i-l;
			if(hd<=tl)
		  	  ans=max(ans,b[i]-b[q[hd]]);
		 }
	 }
	printf("%lld",ans);
	return 0;
}