琪露诺

题意

有编号 0..N 的格子，起点在 0，每次可以从 i 跳到 [i+L, i+R] 中的任意格子。停在格子 i 可以获得 A[i]，当下一步跳到大于 N 的位置时算到达对岸。求能获得的最大冰冻指数。

思路

设 dp[i] 表示到达格子 i 时能获得的最大冰冻指数。想转移到 i，前一个格子 j 必须满足：

text

1i - R <= j <= i - L

朴素做法是对每个 i 枚举所有合法前驱 j。

先看一个可以直接验证想法的朴素解：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39#include <bits/stdc++.h>
using namespace std;

// brute.cpp：直接枚举每个格子的所有前驱，复杂度 O(nr)，只适合小数据。

const int MAXN = 305;
const int NEG_INF = -1000000000;

int n, l, r;
int a[MAXN];
int dp[MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> l >> r;
    for (int i = 0; i <= n; i++) {
        cin >> a[i];
        dp[i] = NEG_INF;
    }
    dp[0] = 0;

    int ans = NEG_INF;
    for (int i = 1; i <= n; i++) {
        for (int j = max(0, i - r); j <= i - l; j++) {
            if (dp[j] != NEG_INF) {
                dp[i] = max(dp[i], dp[j] + a[i]);
            }
        }
        if (i + r > n) {
            ans = max(ans, dp[i]);
        }
    }

    cout << ans << '\n';

    return 0;
}

朴素做法最坏接近 $O(nR)$ ，无法通过 N=2 * 10^5。

观察转移：

text

1dp[i] = A[i] + max(dp[j])    (i-R <= j <= i-L)

这就是滑动窗口最大值。随着 i 增大，合法前驱区间整体向右滑动。用单调队列保存前驱下标，并让队头始终是当前窗口内 dp 最大的位置。

每一轮处理 i 时：

把新进入窗口的 i-L 加入队列；
删除小于 i-R 的过期前驱；
若队列非空，用队头更新 dp[i]；
如果 i+R>N，说明可以从 i 一步跳到对岸，用 dp[i] 更新答案。

注意答案不是固定的 dp[N]，因为最后一步可以直接跳过 N。

样例中 $L=2,R=3$ ，前几项转移如下：

格子 `i`	合法前驱区间	可达前驱最大值	`A[i]`	`dp[i]`
2	`[0,0]`	0	3	3
3	`[0,1]`	0	11	11
4	`[1,2]`	3	7	10
5	`[2,3]`	11	-2	9

队列维护第三列的窗口最大值；格子 3 可以再跳 3 格越过 $N=5$ ，所以答案可取 dp[3]=11。

Python 知识

deque 保存候选下标，队头对应当前最大 dp。
array("q") 紧凑保存权值和 DP，负无穷使用 64 位范围内的 -(1 << 60)。
先加入 i-L、再删除小于 i-R 的下标，和合法前驱区间严格对应。

代码

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28import sys
from array import array
from collections import deque


data = iter(map(int, sys.stdin.buffer.read().split()))
n, left_jump, right_jump = next(data), next(data), next(data)
value = array("q", (next(data) for _ in range(n + 1)))
negative_infinity = -(1 << 60)
dp = array("q", [negative_infinity]) * (n + 1)
dp[0] = 0
queue = deque()
answer = negative_infinity

for i in range(left_jump, n + 1):
    candidate = i - left_jump
    if dp[candidate] != negative_infinity:
        while queue and dp[queue[-1]] <= dp[candidate]:
            queue.pop()
        queue.append(candidate)
    while queue and queue[0] < i - right_jump:
        queue.popleft()
    if queue:
        dp[i] = dp[queue[0]] + value[i]
    if i + right_jump > n:
        answer = max(answer, dp[i])

print(answer)

复杂度

时间复杂度 $O(n)$ ，每个下标最多入队和出队一次。

空间复杂度 $O(n)$ 。

总结

本题的核心是把“能从哪些点跳到当前点”反推成区间 [i-R, i-L]。只要看出转移需要这个区间内的 dp 最大值，就可以用单调队列优化。

目录

题意

思路

Python 知识

代码

复杂度

总结