题目#

琪露诺#

题目描述#

小河可以看作一列格子依次编号为 $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

代码#

1
#include<bits/stdc++.h>
2
const int N = 2e5 + 10;
3
using namespace std;
4
int read()
5
{
6
  int f = 1, x = 0;
7
  char ch = getchar();
8
  while(ch < '0' || ch > '9')
9
  {
10
    if(ch == '-') f = -1;
11
    ch = getchar();
12
  }
13

14
  while(ch >= '0' && ch <= '9')
15
  {
16
    x = x * 10 + ch - '0';
17
    ch = getchar();
18
  }
19
  return f * x;
20
}
21

22

23
int n, L, R;
24
int a[N], f[N];
25

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

28

29
int main()
30
{
31
  n = read(), L = read(), R = read();
32

33
  n ++;//!!!!
34
  for(int i = 1;i <= n;i++) f[i] = -0x3f3f3f3f;
35
  f[1] = 0;
36
  for(int i = 1;i <= n;i++)
37
  {
38
    a[i] = read();
39
  }
40
  int ans = -0x3f3f3f3f;
41
  for(int i = 1;i <= n;i++)
42
  {
43
    if(i - L >= 1)
44
    {
45
      while(t >= h && f[i - L] >= f[qwq[t]]) t--;
46
      qwq[++t] = i - L;
47
      while(qwq[h] < i - R) h++;
48
      f[i] = f[qwq[h]] + a[i];
49
    }
50

51
    if(i + R > n) ans = max(ans, f[i]);
52
  }
53
  printf("%d", ans);
54

55
  return 0;
56
}