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;
}