题解

思路

设 $dp_i$ 表示从格子 $0$ 出发并恰好停在 $i$ 时能获得的最大总和。令 $dp_0=0$，不可达状态为负无穷。转移为

做法

计算 $i$ 前，将新进入窗口的下标 $i-L$ 加入双端队列，并弹出所有 $dp$ 值不大于它的队尾；再删除所有下标小于 $i-R$ 的过期队首。队列中的下标递增、$dp$ 值单调不增，因此队首就是合法前驱的最大值。

被弹出的队尾更早且不优，未来不可能胜过新状态；过期元素恰在离开窗口时删除，所以转移不重不漏。

从最后停留格子 $i$ 能一步离岸，当且仅当 $i+R>N$。因此答案是所有 $i\in[N-R+1,N]$ 的可达 $dp_i$ 最大值，而不一定是 $dp_N$。

复杂度

每个下标至多入队和出队一次，时间复杂度为 $O(N)$，空间复杂度为 $O(N)$。