P1725 琪露诺

洛谷 P1275

$$f_{i} = f_{j}(max) j\in[i - r, i - l]$$

单调队列可解决，代码边界不要考虑错

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

const int N = 2e5 + 10;

int n, l, r;
int a[N], f[N], q[N];

int main(){
	
	memset(f, -0x3f, sizeof f);
	scanf("%d%d%d", &n, &l, &r);
	for(int i = 0; i <= n; i ++)
		scanf("%d", &a[i]);
		
	f[0] = 0;
	for(int i = l; i <= r; i ++)
		f[i] = a[i];
	int hh = 0, tt = 0;
	for(int i = 1; i <= n; i ++){

		if(hh <= tt && i - q[hh] > r - l) hh ++;
		if(f[i] != f[200005]){
			while(hh <= tt && f[q[tt]] <= f[i]) tt --;
			q[++tt] = i;
		}
		
		if(hh <= tt && i + l <= n)
			f[i + l] = f[q[hh]] + a[i + l];
	}
	
	int ans = -0x3f3f3f3f;
	for(int i = n - r + 1; i <= n; i ++)
		ans = max(ans, f[i]);
		
	printf("%d", ans);
	
	return 0;
}