P1725 琪露诺

题目#

琪露诺#

题目描述#

小河可以看作一列格子依次编号为 $0$ 到 $N$，琪露诺只能从编号小的格子移动到编号大的格子。而且琪露诺按照一种特殊的方式进行移动，当她在格子 $i$ 时，她只移动到区间 $[i+L,i+R]$ 中的任意一格。你问为什么她这么移动，这还不简单，因为她是笨蛋啊。

每一个格子都有一个冰冻指数 $A_i$，编号为 $0$ 的格子冰冻指数为 $0$。当琪露诺停留在那一格时就可以得到那一格的冰冻指数 $A_i$。琪露诺希望能够在到达对岸时，获取最大的冰冻指数，这样她才能狠狠地教训那只青蛙。

但是由于她实在是太笨了，所以她决定拜托你帮它决定怎样前进。

开始时，琪露诺在编号 $0$ 的格子上，只要她下一步的位置编号大于 $N$ 就算到达对岸。
$N \le 2\times 10^5$

题解#

设 f [i] 表示到达 i 时候能获得的最大的价值

转移也很容易想到，就是会 T

想一想，可以用单调队列优化 dp

单调队列维护 i-R 到 i-L 区间内的 f 的最大值

(单调队列写的时候几个易错点：
1. 头尾处理的时候用的是 while
2. 想明白单调队列里存的是下标)

!!!! 别忘了初始化！就像这组数据，有的点是走不到的
6 2 2 0 1 -1 1 -1 1 -1
应该为 - 3

代码#

#include<bits/stdc++.h>
const int N = 2e5 + 10;
using namespace std;
int read()
{
	int f = 1, x = 0;
	char ch = getchar();
	while(ch < '0' || ch > '9')
	{
		if(ch == '-') f = -1;
		ch = getchar();
	}
	
	while(ch >= '0' && ch <= '9')
	{
		x = x * 10 + ch - '0';
		ch = getchar();
	}
	return f * x;
}


int n, L, R;
int a[N], f[N];

int qwq[N], h = 1, t = 0;


int main()
{
	n = read(), L = read(), R = read();
	
	n ++;//!!!!
	for(int i = 1;i <= n;i++) f[i] = -0x3f3f3f3f;
	f[1] = 0;
	for(int i = 1;i <= n;i++)
	{
		a[i] = read();
	}
	int ans = -0x3f3f3f3f;
	for(int i = 1;i <= n;i++)
	{
		if(i - L >= 1)
		{
			while(t >= h && f[i - L] >= f[qwq[t]]) t--;
			qwq[++t] = i - L;
			while(qwq[h] < i - R) h++;
			f[i] = f[qwq[h]] + a[i];
		}

		if(i + R > n) ans = max(ans, f[i]);
	}
	printf("%d", ans);
	
	return 0;
}