問題#
琪露诺#
問題の説明#
小川は $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$ の最大値を維持します。
（単調キューを書くときのいくつかの間違いやすい点：
- 先頭と末尾の処理に while を使用すること。
- 単調キューに保存されるのはインデックスであることを理解すること。）
!!!! 初期化を忘れないでください！このデータセットのように、到達できない点があるためです。
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;
}