作为金牌教练，制作一套严谨的 OJ 测试数据需要考虑到算法的各种极端情况。对于“跳跃游戏 VI”，数据生成的重点在于考察单调队列是否能正确维护最大值，以及是否能处理大规模负数导致的路径选择问题。

以下是为你准备的自动化数据生成器。该程序遵循 C++14 标准，采用非递归的单调队列标程逻辑生成 .out 文件，确保在 $N=10^5$ 规模下不会超时。

一、 数据生成器代码 (C++14)

#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <deque>
#include <algorithm>
#include <random>
#include <ctime>

using namespace std;

/**
 * 标程逻辑：用于生成 .out 文件
 * 采用单调队列优化 DP, 时间复杂度 O(N)
 */
long long solve_standard(int n, int k, const vector<int>& nums) {
    if (n == 0) return 0;
    vector<long long> dp(n);
    dp[0] = nums[0];
    deque<int> dq;
    dq.push_back(0);

    for (int i = 1; i < n; ++i) {
        // 1. 弹出不在窗口 [i-k, i-1] 内的决策点
        while (!dq.empty() && dq.front() < i - k) {
            dq.pop_front();
        }
        // 2. 状态转移: 当前最大分 = 窗口内最大 dp + nums[i]
        dp[i] = dp[dq.front()] + nums[i];
        // 3. 维护单调队列 (递减)
        while (!dq.empty() && dp[i] >= dp[dq.back()]) {
            dq.pop_back();
        }
        dq.push_back(i);
    }
    return dp[n - 1];
}

/**
 * 写入测试点文件
 */
void write_test_case(int id, int n, int k, const vector<int>& nums) {
    string in_name = to_string(id) + ".in";
    string out_name = to_string(id) + ".out";

    // 写入输入文件 (.in)
    ofstream fout(in_name);
    fout << n << " " << k << "\n";
    for (int i = 0; i < n; ++i) {
        fout << nums[i] << (i == n - 1 ? "" : " ");
    }
    fout << endl;
    fout.close();

    // 计算并写入输出文件 (.out)
    long long result = solve_standard(n, k, nums);
    ofstream fans(out_name);
    fans << result << endl;
    fans.close();

    cout << "Generated Case " << id << " (N=" << n << ", k=" << k << ")" << endl;
}

int main() {
    mt19937 rng(time(0));
    uniform_int_distribution<int> val_dist(-10000, 10000);

    for (int i = 1; i <= 10; ++i) {
        int n, k;
        vector<int> nums;

        if (i == 1) { // 样例
            n = 6; k = 2;
            nums = {1, -1, -2, 4, -7, 3};
        } 
        else if (i == 2) { // 最小边界 N=1
            n = 1; k = 100;
            nums = {val_dist(rng)};
        }
        else if (i == 3) { // 边界：k=1 (必须一步步走，等同于数组总和)
            n = 1000; k = 1;
            for (int j = 0; j < n; ++j) nums.push_back(val_dist(rng));
        }
        else if (i == 4) { // 边界：k=N (可以从起点跳到任何位置)
            n = 1000; k = 1000;
            for (int j = 0; j < n; ++j) nums.push_back(val_dist(rng));
        }
        else if (i == 5) { // 全正数：最大得分应为全选
            n = 5000; k = 10;
            for (int j = 0; j < n; ++j) nums.push_back(rng() % 10000 + 1);
        }
        else if (i == 6) { // 全负数：测试寻找“损失最小”的路径
            n = 5000; k = 10;
            for (int j = 0; j < n; ++j) nums.push_back(-(rng() % 10000 + 1));
        }
        else if (i == 7) { // 锯齿形：极大正数与极小负数交替
            n = 10000; k = 100;
            for (int j = 0; j < n; ++j) nums.push_back(j % 2 == 0 ? 10000 : -10000);
        }
        else if (i <= 8) { // 随机中等规模
            n = 10000; k = rng() % 5000 + 1;
            for (int j = 0; j < n; ++j) nums.push_back(val_dist(rng));
        }
        else if (i <= 10) { // 极限规模：N=10^5, K=10^5
            n = 100000; k = rng() % 100000 + 1;
            for (int j = 0; j < n; ++j) nums.push_back(val_dist(rng));
        }

        write_test_case(i, n, k, nums);
    }
    return 0;
}

二、 测试点设计思路（创建 OJ 必读）

作为教练，这 10 组数据旨在全方位检测选手的代码健壮性：

三、 考场避坑建议

1. 数据溢出： 虽然 $nums[i]$ 只有 $10^4$，但 $10^5$ 个数相加会达到 $10^9$。虽然 int 最大支持 $2 \times 10^9$，但考虑到中间计算和可能的变体，金牌选手在处理此类 DP 时一律强制使用 long long。

2. 单调队列的存储： 队列中务必存储下标 (index) 而非 $dp$ 值。只有存储下标，你才能通过 dq.front() < i - k 准确判断决策点是否已经“过期”。

3. 常数优化： 如果在正式比赛中 $N$ 增加到 $10^6$，std::deque 的开销会变得明显。建议熟练掌握数组模拟双端队列的写法，那能让你的程序运行速度提升数倍。

4. 非递归安全： 本生成器和标程算法完全基于迭代（Loops），不涉及任何递归调用，即便在系统栈空间极其有限的评测环境下也能稳定运行。

这份生成器生成的 .in 和 .out 文件完全符合 NOI 竞赛标准，你可以直接打包上传至 OJ 系统。加油！

你好，同学！这道题是单调队列优化动态规划（DP）的经典模板题。在 NOI 竞赛中，掌握这种优化技巧是进入提高组复赛并在 DP 题目中拿高分的关键。

以下是基于 C++14 标准 的满分参考代码，采用了 $O(N)$ 均摊时间复杂度 的单调队列解法。

一、 跳跃游戏 VI 标准题解 (C++14)

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

using namespace std;

/**
 * 题目：跳跃游戏 VI
 * 核心：单调队列优化 DP
 * 
 * 易错点预警：
 * 1. 数据类型：虽然单项最高 10^4，但 10^5 个数累加可能接近 10^9。
 *    在 NOI 竞赛中，涉及累加的 DP 建议一律开 long long。
 * 2. 窗口边界：窗口范围是 [i-k, i-1]，弹出队首时判断条件是 dq.front() < i - k。
 * 3. 队列存储内容：队列中存储下标 (index)，方便判断是否“过期”。
 */

void solve() {
    int n, k;
    if (!(cin >> n >> k)) return;

    vector<int> nums(n);
    for (int i = 0; i < n; ++i) {
        cin >> nums[i];
    }

    // dp[i] 表示跳到下标 i 时能获得的最大得分
    vector<long long> dp(n, 0);
    dp[0] = nums[0];

    // 单调队列，存储下标，维持对应 dp 值的单调递减
    deque<int> dq;
    dq.push_back(0);

    for (int i = 1; i < n; ++i) {
        // 1. 检查队首下标是否已经超出了跳跃范围 k
        // 如果队首下标小于 i - k，说明从那个位置跳不到当前的 i
        while (!dq.empty() && dq.front() < i - k) {
            dq.pop_front();
        }

        // 2. 状态转移：当前最大得分 = 之前的最大得分 + 当前格子的分数
        // 队首始终是窗口 [i-k, i-1] 内 dp 值最大的下标
        dp[i] = dp[dq.front()] + nums[i];

        // 3. 维护队列的单调递减性：
        // 如果当前 dp[i] 比队尾对应的 dp 值大，说明队尾已经没用了。
        // 因为 dp[i] 既比它大，又比它“年轻”（能覆盖更远的范围）。
        while (!dq.empty() && dp[i] >= dp[dq.back()]) {
            dq.pop_back();
        }
        
        // 4. 将当前下标入队
        dq.push_back(i);
    }

    cout << dp[n - 1] << endl;
}

int main() {
    // NOI 竞赛必备优化：加速 I/O 效率
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    solve();

    return 0;
}

二、 复杂度分析思考过程

1. 时间复杂度：$O(N)$

• 分析：虽然程序中有嵌套的 while 循环，但我们采用均摊分析法。数组中的每一个下标 i 都会：
  • 被 push_back 进入队列一次。
  • 最多被 pop_front 弹出一次。
  • 或者最多被 pop_back 弹出一次。
• 结论：总的操作次数是 $O(N)$ 级别的，与跳跃长度 $K$ 无关。对于 $N=10^5$ 的规模，能在 0.1s 内轻松解决。

2. 空间复杂度：$O(N)$

• 分析：我们需要一个 dp 数组存储 $N$ 个结果，单调队列在最坏情况下存储 $K$ 个元素。
• 结论：总空间复杂度为 $O(N)$。在 256MB 的限制下，10^5 个 long long 仅占约 0.8MB，非常安全。

三、 时间复杂度优化建议 (NOI 进阶)

如果在更高难度的题目中，$N$ 达到了 $10^6$ 甚至更高，或者时限非常苛刻（如 0.2s），可以进行以下优化：

1. 手动模拟双端队列 (Manual Deque)： std::deque 的内存分配机制（块状存储）会带来一定的常数开销。使用原生数组模拟队列是金牌选手的常用手段：

   int q[1000005]; 
   int head = 0, tail = -1;
   // 入队：q[++tail] = i;
   // 队首弹出：head++;
   // 队尾弹出：tail--;
   

   数组模拟的 deque 在速度上通常比 STL 快 2-3 倍。

2. 原地滚动优化： 由于 $dp[i]$ 只依赖于前 $K$ 个值，理论上可以使用滑动数组将空间优化到 $O(K)$。但在本题 $N=10^5$ 的量级下，直接开 $O(N)$ 数组的逻辑更简单，不容易在比赛中写挂。

3. 避免 endl： 代码中使用了 endl。在输出量极大时，endl 会强制刷新缓冲区，导致速度极慢。建议改用 '\n'。

四、 读题关键词总结

在 NOI 考场上，当你看到以下关键词组合时，应立即联想到单调队列优化 DP：

1. “最大/最小得分/和”：暗示这是最优化问题，优先考虑动态规划。
2. “最多跳 $K$ 步” / “在窗口范围内”：意味着 $dp[i]$ 的决策点来自于一个长度固定的滑动区间。
3. “$N$ 和 $K$ 很大 ($10^5$ 及以上)”：排除 $O(N \cdot K)$ 的暴力 DP。必须寻找线性 $O(N)$ 或 $O(N \log N)$ 的优化方案。

教练寄语： 单调队列优化的精髓在于：“如果一个决策点不仅比你旧，还没你强，那它就永远不可能成为最优解。” 这种“优胜劣汰”的逻辑是解决区间最值问题的万能钥匙。去完成它吧！