题解 | #时空漫游者的能量跳跃#

题目链接

时空漫游者的能量跳跃

题目描述

一位时空漫游者需要从路径的起点信标 $0$ 跳跃到终点信标 $N-1$ 。路径上共有 $N$ 个信标，每个信标 $i$ 拥有能量值 $E[i]$ 。

漫游者从信标 $i$ 出发，下一步可以跳跃到区间 $[i+1, i+k]$ 内的任意一个信标，其中 $k$ 是最大跳跃距离。

任务是规划一条从信标 $0$ 到信标 $N-1$ 的路径，使得收集到的总能量最大化。

输入:

第一行是最大跳跃距离 $k$ 。
第二行是信标总数 $N$ 。
第三行是 $N$ 个整数，代表每个信标的能量值 $E[i]$ 。

输出:

一个整数，代表能收集到的最大总能量。

解题思路

这是一个典型的动态规划问题，旨在寻找一条最优路径以获得最大累积值。

状态定义

我们定义一个数组 $dp$ ，其中 $dp[i]$ 表示跳跃到第 $i$ 个信标时能收集到的最大总能量。我们的最终目标是计算出 $dp[N-1]$ 。

状态转移方程

要计算 $dp[i]$ ，我们需要考虑所有可能的前驱信标。根据题目规则，我们可以从位于区间 $[i-k, i-1]$ 内的任意信标 $j$ 跳跃到信标 $i$ 。为了使到达 $i$ 的总能量最大化，我们应该从具有最大累积能量的那个前驱信标 $j$ 跳过来。因此，状态转移方程为： $dp[i] = E[i] + \max_{ \max(0, i-k) \le j < i } \{ dp[j] \}$

基础情况

旅程从信标 $0$ 开始，所以 $dp[0] = E[0]$ 。

优化

直接根据状态转移方程计算的时间复杂度为 $O(N \cdot k)$ ，因为对于每个 $i$ ，都需要遍历 $k$ 个前驱状态。当 $N$ 和 $k$ 很大时，这可能会超时。

我们可以观察到，计算 $\max\{dp[j]\}$ 的过程实际上是在一个大小为 $k$ 的滑动窗口内寻找最大值。这个问题可以使用 单调队列 (Monotonic Queue) 进行优化。

我们使用一个双端队列（deque），它将存储信标的索引。该队列将始终保持其对应 $dp$ 值的单调递减性（队首的 $dp$ 值最大）。

在计算 $dp[i]$ 时，首先从队首移除所有不在 $[i-k, i-1]$ 窗口内的索引。
此时，队首的索引 $j$ 对应的 $dp[j]$ 就是当前窗口内的最大值。我们用它来计算 $dp[i]$ 。
为了维护队列的单调性，从队尾开始，移除所有 $dp$ 值小于或等于新计算出的 $dp[i]$ 的索引。
将当前索引 $i$ 加入队尾。

通过这种方式，每个索引最多入队和出队一次，寻找窗口最大值的时间复杂度从 $O(k)$ 降为均摊 $O(1)$ 。

代码

c++
java
python

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

using namespace std;

int main() {
    int k, n;
    cin >> k;
    cin >> n;
    vector<long long> E(n);
    for (int i = 0; i < n; ++i) {
        cin >> E[i];
    }

    if (n == 0) {
        cout << 0 << endl;
        return 0;
    }

    vector<long long> dp(n);
    deque<int> q; // 单调队列，存储索引

    dp[0] = E[0];
    q.push_back(0);

    for (int i = 1; i < n; ++i) {
        // 移除窗口外的旧索引
        if (!q.empty() && q.front() < i - k) {
            q.pop_front();
        }
        
        // 计算 dp[i]，队首元素是窗口内的最大值
        dp[i] = E[i] + dp[q.front()];

        // 维护队列的单调递减性
        while (!q.empty() && dp[q.back()] <= dp[i]) {
            q.pop_back();
        }
        q.push_back(i);
    }

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

    return 0;
}

import java.util.Scanner;
import java.util.Deque;
import java.util.LinkedList;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int k = sc.nextInt();
        int n = sc.nextInt();
        long[] E = new long[n];
        for (int i = 0; i < n; i++) {
            E[i] = sc.nextLong();
        }

        if (n == 0) {
            System.out.println(0);
            return;
        }

        long[] dp = new long[n];
        Deque<Integer> q = new LinkedList<>(); // 单调队列，存储索引

        dp[0] = E[0];
        q.addLast(0);

        for (int i = 1; i < n; i++) {
            // 移除窗口外的旧索引
            if (!q.isEmpty() && q.peekFirst() < i - k) {
                q.removeFirst();
            }

            // 计算 dp[i]，队首元素是窗口内的最大值
            dp[i] = E[i] + dp[q.peekFirst()];

            // 维护队列的单调递减性
            while (!q.isEmpty() && dp[q.peekLast()] <= dp[i]) {
                q.removeLast();
            }
            q.addLast(i);
        }

        System.out.println(dp[n - 1]);
    }
}

import collections

# 读取输入
k = int(input())
n = int(input())
E = list(map(int, input().split()))

if n == 0:
    print(0)
else:
    dp = [0] * n
    q = collections.deque() # 单调队列，存储索引

    dp[0] = E[0]
    q.append(0)

    for i in range(1, n):
        # 移除窗口外的旧索引
        if q and q[0] < i - k:
            q.popleft()
        
        # 计算 dp[i]，队首元素是窗口内的最大值
        dp[i] = E[i] + dp[q[0]]

        # 维护队列的单调递减性
        while q and dp[q[-1]] <= dp[i]:
            q.pop()
        q.append(i)

    print(dp[n - 1])

算法及复杂度

算法：动态规划 + 单调队列优化
时间复杂度： $O(N)$ ，因为每个信标的索引最多入队和出队一次。
空间复杂度： $O(N)$ ，主要用于存储 $dp$ 数组。单调队列的空间复杂度为 $O(k)$ 。