labuladong讲解

你好，同学。欢迎来到 NOI 提高组算法专题训练。

今天我们要攻克的是 “动态规划 + 单调队列优化” 的经典进阶题目：跳跃游戏 VI。这道题是理解单调队列如何将 $O(NK)$ 复杂度优化至 $O(N)$ 的标准范式，是 NOI 竞赛中必须掌握的“肌肉记忆”级算法。

一、 预备知识点

在动手前，请确保你已经掌握：

1. 动态规划（DP）：理解状态转移方程的推导。
2. 滑动窗口最值：如何在 $O(1)$ 均摊时间内获取区间最大值。
3. 单调队列（Monotonic Queue）：利用双端队列 std::deque 维护元素的单调性。
4. C++ STL std::deque：常用操作 push_back, pop_back, pop_front, front。

二、 NOI 竞赛题目描述

题目名称：跳跃游戏 VI (Jump Game VI) 时间限制：1.0s 内存限制：256MB

【问题描述】 给你一个下标从 $0$ 开始的整数数组 $nums$ 和一个整数 $k$。 你一开始站的位置是下标 $0$。在每一步中，你最多可以往前跳 $k$ 步，但你不能跳出数组的边界。也就是说，如果你在下标 $i$，你可以跳到满足 $i + 1 \le j \le \min(i + k, n - 1)$ 的任意下标 $j$。 你的目标是到达数组最后一个下标 $n - 1$。你的得分是你途径的所有数字之和。 请你返回能够得到的 最大得分。

【输入格式】 第一行包含两个整数 $n$ 和 $k$，分别表示数组长度和最大跳跃步数。 第二行包含 $n$ 个整数，表示数组 $nums$。

【输出格式】 输出一个整数，表示到达终点能获得的最大得分。

【样例输入】

6 2
1 -1 -2 4 -7 3

【样例输出】

7

【数据范围与约定】

• $1 \le n, k \le 10^5$
• $-10^4 \le nums[i] \le 10^4$
• 数据保证所有计算结果在 long long 范围内。

三、 启发式思路引导：草稿纸上的推演

1. 朴素 DP 状态转移

设 $dp[i]$ 为到达下标 $i$ 时能获得的最高得分。

• 状态转移方程：$dp[i] = nums[i] + \max(dp[j])$，其中 $\max(0, i - k) \le j < i$。
• 起始条件：$dp[0] = nums[0]$。
• 目标：$dp[n-1]$。

2. 性能瓶颈分析

对于每一个 $i$，我们都需要在前 $k$ 个 $dp$ 值里找最大值。

• 如果直接遍历：时间复杂度为 $O(N \times K)$。
• 在 $N, K = 10^5$ 时，计算量达到 $10^{10}$，在 1.0s 内必然超时（TLE）。

3. 单调队列优化

我们需要在滑动窗口内动态维护最大值。

• 思考：如果 $dp[a] < dp[b]$ 且 $a < b$，那么只要 $b$ 还在窗口内，$a$ 就不可能成为最大值的候选。
• 方案：维护一个下标的单调递减队列。队列头部始终存储当前窗口内对应的最大 $dp$ 值的下标。

四、 算法流程图（伪代码逻辑）

为了在 Mermaid 中避开特殊字符报错，我们使用圆括号代替方括号，并用简洁文字描述。

graph TD
    Start(开始处理 DP 数组) --> Init(初始化 dp_0 等于 nums_0)
    Init --> DequeInit(将下标 0 放入双端队列 dq)
    DequeInit --> LoopStart{遍历 i 从 1 到 n 减 1}
    LoopStart -- 遍历结束 --> EndResult(输出 dp_n减1)
    
    LoopStart -- 正在处理 i --> PopFront{队首下标是否小于 i 减 k}
    PopFront -- 是 --> PopAction(从队首弹出过时下标)
    PopAction --> CalcDP
    PopFront -- 否 --> CalcDP(dp_i 等于 nums_i 加上 dp_队首)
    
    CalcDP --> MaintainQueue{循环- 若当前 dp_i 大于等于 dp_队尾}
    MaintainQueue -- 是 --> PopBack(从队尾弹出较小值的下标)
    PopBack --> MaintainQueue
    MaintainQueue -- 否 --> PushIdx(将下标 i 压入队尾)
    PushIdx --> LoopStart

五、 复杂度分析与时间复杂度优化建议

• 时间复杂度分析：
  • 虽然有嵌套的 while 循环，但每个下标最多只会被 push_back 进队列一次，也最多只会被 pop 弹出一次。
  • 均摊复杂度：总时间复杂度为 $O(n)$。
• 空间复杂度分析：
  • 需要存储 dp 数组和单调队列，复杂度为 $O(n)$。

NOI 考场优化建议：

1. 数据类型：由于分数累加，虽然 $10^5 \times 10^4 = 10^9$ 在 int 范围内，但为了保险起见，建议统一使用 long long 存储 $dp$ 数组。
2. 常数优化：如果 $N=10^6$ 或时限更紧，std::deque 可能会因为内存分配略慢。可以手写数组模拟双端队列（使用 head 和 tail 指针），这在 NOI 竞赛中是更稳健的做法。

六、 读题关键词总结

在处理此类“跳跃”或“连续选择”问题时，请留意以下关键词：

1. “最大得分”：提示使用动态规划。
2. “最多往前跳 k 步”：提示状态转移来自于一个滑动窗口。
3. “$N, K \le 10^5$”：这是强制要求将 $O(NK)$ 优化至 $O(N)$ 或 $O(N \log N)$ 的信号。

教练寄语： 单调队列优化 DP 是处理线性规划类问题的重器。它的核心在于**“及时止损”**：踢掉过期的（队首），踢掉无能的（队尾）。掌握了这个思想，你就能看穿大多数滑动窗口类优化。去实现它吧！