3147. 从魔法师身上吸取的最大能量

发表于 分类于 阅读次数： Waline： 本文字数： 919 阅读时长 ≈ 3 分钟

考点

  • 线性DP

思路

一、问题抽象与建模

给定一个长度为 \(n\) 的数组： \[ \text{energy}[0 \ldots n-1] \] 以及一个正整数 \(k\)。

规则如下：

  • 可以选择任意起点 \(s\)
  • 从 \(s\) 出发，每一步必须跳到 \(s+k, s+2k, \ldots\)
  • 一直跳到无法继续为止
  • 路径上经过的所有位置的能量值 必须全部累加（正负都算）
  • 目标是最大化总能量

关键观察 1：路径结构是“模 \(k\) 的链”

任意一条合法路径，索引序列必然是： \[ s,\ s+k,\ s+2k,\ \ldots \] 因此，数组可以被划分为 \(k\) 条互不相交的链： \[ \{ i \mid i \equiv r \pmod{k} \},\quad r=0,1,\ldots,k-1 \] 每条路径只会存在于某一条链中。

关键观察 2：路径必须走到“链尾”

对于任意起点 \(s\)，路径的终点 \(e\) 一定满足： \[ e + k \ge n \] 即： \[ e \in [\,n-k,\ n-1\,] \] 所有合法路径的终点，只可能落在数组的最后 \(k\) 个位置。

这一点在后续答案控制中至关重要。

二、动态规划状态设计

采用 前向 DP + 结尾过滤 的建模方式。

状态定义

令： \[ f[i] = \text{在同一模 } k \text{ 链上，以 } i \text{ 作为当前结点时的最大可达能量} \] 这里的“最大”指的是： 允许在链中选择一个最优起点，一路跳到 \(i\)。

状态转移

位置 \(i\) 有两种可能来源：

  1. 从当前位置重新开始 \[ f[i] = \text{energy}[i] \]

  2. 从同一链上的前一个结点跳过来 若 \(i-k \ge 0\)，则： \[ f[i] = f[i-k] + \text{energy}[i] \]

综合取最大值： \[ f[i] = \max\bigl(\text{energy}[i],\ f[i-k] + \text{energy}[i]\bigr) \] 这一步等价于：

在每一条模 \(k\) 链上，做一次“允许重新开始”的最大前缀和 DP。

三、答案的关键控制：只在合法结尾取最大

注意： 上述 DP 允许中途重新开始，因此 \(f[i]\) 并不一定代表一条合法完整路径。

为保证合法性，必须利用“路径必须走到链尾”的约束。

合法结尾条件

根据前面的观察，合法路径的终点 \(i\) 必须满足： \[ i \ge n-k \] 因此，最终答案为： \[ \max_{i \in [n-k,\ n-1]} f[i] \] 也就是说：

  • DP 过程中允许自由截断
  • 但只在“无法再跳”的位置统计答案

这一“结尾控制”使得前向 DP 的结果与题目要求严格一致。

四、正确性直觉说明

  • DP 转移保证： \(f[i]\) 是“到达 \(i\) 的所有合法前缀路径中能量最大的一个”
  • 终点筛选保证： 只统计那些 已经被迫走到终点的路径
  • 因此，每一条被计入答案的路径，必然：
    • 起点合法
    • 跳跃规则合法
    • 无法提前停止
    • 能量和最大

五、时间与空间复杂度

  • 时间复杂度： \[ O(n) \]

  • 空间复杂度： \[ O(n) \]

满足题目最优要求。

六、AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    static const int maxn = 1e5 + 5;

    int maximumEnergy(vector<int>& energy, int k) {
        int f[maxn];                // f[i]: 同一模 k 链上，到达 i 的最大能量
        int n = energy.size();
        int res = INT_MIN >> 1;     // 最终答案，只在合法结尾更新

        // 使用 1-based 索引，energy[i-1] 对应位置 i
        for (int i = 1; i <= n; ++i) {
            // 情况 1：从当前位置重新开始
            f[i] = energy[i - 1];

            // 情况 2：从同一模 k 链的前一个位置跳过来
            if (i > k)
                f[i] = max(f[i], f[i - k] + energy[i - 1]);

            // 只有当 i 位于最后 k 个位置时，
            // 才可能是“无法继续跳”的合法终点
            if (i > n - k)
                res = max(res, f[i]);
        }

        return res;
    }
};