题解 P1725 【琪露诺】(DP + 单调队列)

1. 题目简述

琪露诺从编号为 $0$ 的格子出发，要跳过编号为 $N$ 的格子（即到达 $>N$ 的位置）。在位置 $i$ 时，她只能跳到区间 $[i+L, i+R]$ 中的任意一格。每个格子都有一个冰冻指数 $A_i$ ，求跳到对岸时能获得的最大冰冻指数之和。

数据范围： $N \le 2 \times 10^5$ ， $-1000 \le A_i \le 1000$ 。

2. 思路分析

朴素 DP (TLE 预警)

设 $dp[i]$ 表示琪露诺到达编号为 $i$ 的格子时，所能获得的最大冰冻指数。

初始状态： $dp[0] = 0$ （起点不获得指数，或者根据题意 $A_0$ 的处理，题目说 $0$ 号格子指数为 $0$ ，且 $0$ 号是起点），其余 $dp$ 值为负无穷（表示不可达）。
转移方程： 想要到达 $i$ ，必须从某个位置 $j$ 跳过来。根据题目规则： $j + L \le i \le j + R$ 。反推 $j$ 的范围： $i - R \le j \le i - L$ 。
$dp[i] = A_i + \max(dp[j]) \quad \text{其中 } i-R \le j \le i-L$
答案： 只要是从某个位置 $i$ 能跳到对岸（即 $i + R > N$ ），那么 $dp[i]$ 就是一个可能的答案。最终答案为 $\max(dp[i])$ ，其中 $N-R+1 \le i \le N$ 。

复杂度分析： 外层循环枚举 $i$ 从 $L$ 到 $N$ ，内层循环枚举 $j$ 。时间复杂度为 $O(N \times (R-L))$ 。当 $R-L$ 很大时，复杂度接近 $O(N^2)$ ，对于 $2 \times 10^5$ 的数据肯定会超时。

单调队列优化 (Accept)

观察转移方程：

dp[i] = A_i + \max(dp[j])

我们需要在区间

[i-R, i-L]

中找到最大的

dp[j]

。当

i

变成

i+1

时，这个区间变成了

[i+1-R, i+1-L]

。也就是区间整体向右滑动了一格。

这正是滑动窗口最大值模型！我们可以用单调队列来维护区间 $[i-R, i-L]$ 内 $dp$ 值的最大值。

具体步骤：

维护一个单调递减的队列（存放下标），队头对应的 $dp$ 值最大。
枚举 $i$ 从 $L$ 到 $N$ ：
- 入队候选人：当前 $i$ 对应的左边那个新进入窗口范围的位置是 $pos = i - L$ 。我们需要将 $pos$ 放入队列。
- 维护单调性：如果 $dp[pos] \ge dp[队尾]$ ，则弹出队尾，直到队列单调递减。
- 移除过期元素：窗口的左边界是 $i - R$ 。如果 $队头下标 < i - R$ ，说明队头已经滑出窗口，弹出队头。
- 计算 DP： $dp[i] = A[i] + dp[队头]$ 。
- 更新答案：如果当前 $i$ 满足 $i + R > N$ ，说明从 $i$ 可以跳到对岸，用 $dp[i]$ 更新最终答案。

时间复杂度： $O(N)$ 。

3. 细节处理

初始化： $dp$ 数组要初始化为一个很小的负数（如 -1e9），因为 $A_i$ 可能是负数，且为了区分“不可达”状态。
数据范围： $N=200000$ ，答案范围在 int 范围内，但为了防止加法溢出，用 int 即可（题目保证答案不超过 int 范围）。
答案区间：并不是 $dp[N]$ ，而是所有能一步跳过 $N$ 的位置的 $dp$ 最大值。

4. 图解推演

假设 $N=5, L=2, R=3$ ，数组 $A: [0, 12, 3, 11, 7, -2]$ 。初始化 $dp[0]=0$ ，其余 $-\infty$ 。

i	窗口范围 $[i-R, i-L]$	新入队下标 $(i-L)$	队列状态 (存下标)	队头	$dp[i] = A[i] + dp[队头]$	更新答案?
2	$[-1, 0]$	0	`{0}`	0	$3 + dp[0] = 3$	否
3	$[0, 1]$	1	`{1}` ( $dp[1]=-\infty$ , 忽略或处理) 其实 $1$ 不可达，这里简化处理，队列里只有 `{0}`	0	$11 + dp[0] = 11$	是 ( $3+3>5$ )
4	$[1, 2]$	2	比较 $dp[2]$ 与 $dp[0]$ 。 $3>0$ , 0出队。队列 `{2}`	2	$7 + dp[2] = 10$	是 ( $4+3>5$ )
5	$[2, 3]$	3	比较 $dp[3]$ 与 $dp[2]$ 。 $11>3$ , 2出队。队列 `{3}`	3	$-2 + dp[3] = 9$	是 ( $5+3>5$ )

最终比较所有满足条件的 $dp$ 值： $11, 10, 9$ ，最大值为 11。

5. AC 代码

cpp

#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>

using namespace std;

const int MAXN = 200005;
const int INF = -2e9; // 初始化负无穷

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

int main() {
    // 优化 I/O
    ios::sync_with_stdio(false);
    cin.tie(0);

    if (!(cin >> n >> l >> r)) return 0;

    // 读入 A_i，注意题目说第 i 个数是编号 i-1，
    // 其实就是从 0 到 N 输入
    for (int i = 0; i <= n; i++) {
        cin >> a[i];
    }

    // 初始化 DP 数组
    for (int i = 0; i <= n; i++) dp[i] = INF;
    dp[0] = 0; // 起点

    // 单调队列，存储下标
    deque<int> q;
    
    // 最终答案，初始化为很小的数
    int ans = INF;

    // DP 过程，i 从 L 开始，因为 0+L 是第一个能到达的点
    for (int i = L; i <= n; i++) {
        // 1. 新的候选下标进入视野： j = i - L
        // 这个位置作为起跳点，可以跳到 i
        int candidate = i - L;
        
        // 只有当 candidate 是可达的时候，才有资格进入队列
        // 虽然不可达的点值为 INF，比较时会被弹出去，但为了逻辑严谨
        if (dp[candidate] != INF) {
            // 维护单调递减队列 (如果新来的比队尾优，删队尾)
            while (!q.empty() && dp[q.back()] <= dp[candidate]) {
                q.pop_back();
            }
            q.push_back(candidate);
        }

        // 2. 移除过期元素
        // 能跳到 i 的最远位置是 i - R
        // 如果队头下标 < i - R，说明队头跳不到 i 了
        if (!q.empty() && q.front() < i - r) {
            q.pop_front();
        }

        // 3. 转移状态
        // 如果队列不为空，队头就是当前窗口 [i-R, i-L] 内的最优解
        if (!q.empty()) {
            dp[i] = dp[q.front()] + a[i];
        }

        // 4. 更新最终答案
        // 如果从当前位置 i 再跳一步(最小L，最大R)能超过 N，则 i 是合法的最后一步
        // 只要区间 [i+L, i+R] 与 [N+1, +inf] 有交集
        // 即 i + R > N
        if (i + R > n) {
            ans = max(ans, dp[i]);
        }
    }

    cout << ans << endl;

    return 0;
}

6. 总结

模型识别：区间长度固定的最值转移 $\rightarrow$ 单调队列。
坐标变换：仔细处理 $i, L, R$ 的关系，确定“入队元素”是 $i-L$ ，“过期边界”是 $i-R$ 。
边界条件：注意 $dp$ 初始化的负无穷要足够小，且判断答案时要看清楚题目定义的“到达对岸”。

琪露诺

目录