题解 | 时空漫游者的能量跳跃（动态规划+滑动窗口）

// C++版本
// 算法：动态规划 + 滑动窗口
// 数据结构：单调队列
// 空间复杂度：O(n)
// 时间复杂度：O(n)

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

int travel(const std::vector<int>& energy, const int k) {
    const int size = static_cast<int>(energy.size());

    // 动态规划辅助数组
    std::vector<int> dp(size);
    dp[0] = energy[0];

    // 单调队列（注意：保存下标不是值）
    std::deque<int> dq;
    dq.push_back(0);

    for (int i = 1; i < size; ++i) {
        // 超出范围的删除
        while (!dq.empty() && dq.front() < i - k) {
            dq.pop_front();
        }

        dp[i] = energy[i] + dp[dq.front()];

        // 比dp[i]小的都删除，因为它们未来也不可能是最大值
        while (!dq.empty() && dp[i] >= dp[dq.back()]) {
            dq.pop_back();
        }

        // 入队
        dq.push_back(i);
    }

    return  dp[size - 1];
}

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

    int k, n;
    std::cin >> k >> n;

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

    std::cout << travel(energy, k) << std::endl;

    return 0;
}