P1725 Cirno - histcat

Problem#

Cirno#

Problem Description#

The small river can be viewed as a series of cells numbered from $0$ to $N$, and Cirno can only move from a cell with a smaller number to a cell with a larger number. Moreover, Cirno moves in a special way; when she is at cell $i$, she can only move to any cell in the range $[i+L,i+R]$. You may wonder why she moves this way, and it's simple: because she is a fool.

Each cell has a freezing index $A_i$, with the cell numbered $0$ having a freezing index of $0$. When Cirno stays in a cell, she can obtain the freezing index $A_i$ of that cell. Cirno hopes to obtain the maximum freezing index by the time she reaches the other side, so she can teach that frog a lesson.

However, since she is quite foolish, she has decided to ask you to help her decide how to proceed.

At the start, Cirno is on cell numbered $0$, and as long as her next position number is greater than $N$, she has reached the other side.
$N \le 2\times 10^5$

Solution#

Let f[i] represent the maximum value that can be obtained when reaching i.

The transition is also easy to think of, which will be T.

Think about it; a monotonic queue can be used to optimize the dp.

The monotonic queue maintains the maximum value of f in the range from i-R to i-L.

(Points to note when writing the monotonic queue:

Use while for head and tail processing.
Understand that the monotonic queue stores indices.)

!!!! Don't forget to initialize! Just like this set of data, some points are unreachable.
6 2 2 0 1 -1 1 -1 1 -1
Should be -3

Code#

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