3186. 施咒的最大总伤害

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

考点

  • 线性DP

思路

一、问题抽象与建模

给定一个整数数组 power，每个元素表示一次施法所能造成的伤害值。 可以选择任意多个施法，但 若选择了伤害值为 x 的施法，则不能再选择伤害值为 x-1、x-2、x+1、x+2 的施法。

目标是在满足上述约束的前提下，使得总伤害最大化。

二、核心观察与等价转化

1. 同值施法的等价性

若某个伤害值 x 在数组中出现了多次：

  • 选择其中一次或多次 不会引入新的冲突
  • 因为冲突只取决于 数值差，而非次数

因此：

对于同一个伤害值 x，要么全部选，要么全部不选。

于是可以将原问题转化为：

  • 对每一个不同的伤害值 x，计算其总贡献 \[ \text{gain}(x) = x \times (\text{出现次数}) \]

2. 排序与去重

将数组排序并去重，得到严格递增序列： \[ v_1 < v_2 < \dots < v_n \] 并定义： \[ g_i = \text{gain}(v_i) \] 此时问题变为：

在序列 \((v_i, g_i)\) 中选择若干项，使得任意被选的两个值之差 \(\ge 3\)，并最大化 \(\sum g_i\)。

三、动态规划设计

1. 状态定义

定义状态： \[ f[i] = \text{只考虑前 } i \text{ 个不同伤害值（} v_1 \sim v_i \text{）时的最大总伤害} \] 最终答案为 f[n]。

2. 状态转移分析

对第 i 个伤害值 \(v_i\)，有两类选择：

情况一：不选 \(v_i\)

\[ f[i] = f[i-1] \]

情况二：选 \(v_i\)

设当前收益为 \(g_i\)。

由于冲突范围是 ±1、±2，因此在 更小的一侧，最多只有两个整数值会与 \(v_i\) 冲突：

  • \(v_i - 1\)
  • \(v_i - 2\)

也就是说：

  • 若 \(v_i - v_{i-1} \ge 3\)，则可以直接接在 f[i-1] 后
  • 否则，可能需要回退 1～2 个位置

由于值是整数，且冲突范围固定为 2，可以证明：

能与 \(v_i\) 共存的最右前缀，一定落在 i-1、i-2 或 i-3 之中。

于是枚举以下三种合法拼接方式：

  1. 若 \(v_i - v_{i-1} \ge 3\)： \[ f[i] = f[i-1] + g_i \]

  2. 否则若 \(v_i - v_{i-2} \ge 3\)： \[ f[i] = f[i-2] + g_i \]

  3. 否则（必然有 \(v_i - v_{i-3} \ge 3\)）： \[ f[i] = f[i-3] + g_i \]

3. “只选当前值”的必要性

还需特别注意一种情况：

  • 当前值 \(v_i\) 与前面的所有值都冲突
  • 最优策略是 抛弃前面所有选择，仅选 \(v_i\)

因此必须比较： \[ f[i] = \max(f[i],\ g_i) \]

4. 完整转移式

综合以上分析，转移逻辑为： \[ \begin{aligned} f[i] = \max \big(& f[i-1],\ g_i, \\ & f[i-1] + g_i \quad \text{(若 } v_i - v_{i-1} \ge 3), \\ & f[i-2] + g_i \quad \text{(若 } v_i - v_{i-2} \ge 3), \\ & f[i-3] + g_i \big) \end{aligned} \]

四、算法复杂度

  • 排序：\(O(n \log n)\)
  • 去重与 DP：\(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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Solution {
public:
    static const int maxn = 1e5 + 5;

    long long maximumTotalDamage(vector<int>& power) {
        // mp[x] = x * 出现次数（总收益）
        unordered_map<int, long long> mp;

        // 排序，方便去重与差值判断
        sort(power.begin(), power.end());

        // 聚合同值伤害
        for (int x : power)
            mp[x] += x;

        // 去重，power[0..n-1] 为不同伤害值
        int n = unique(power.begin(), power.end()) - power.begin();

        // f[i]：只考虑前 i 个不同伤害值的最大总伤害
        long long f[maxn];

        // 初始化：只选第一个伤害值
        f[1] = mp[power[0]];

        for (int i = 2; i <= n; ++i) {
            long long x = power[i - 1]; // 当前伤害值
            long long y = mp[x];        // 当前总收益

            // 情况 1：不选 x
            // 情况 2：只选 x
            f[i] = max(f[i - 1], y);

            // 情况 3：选 x + 合法前缀
            if (x - power[i - 2] >= 3) {
                // 可以直接接在 f[i-1] 后
                f[i] = max(f[i], f[i - 1] + y);
            } else if (i >= 3 && x - power[i - 3] >= 3) {
                // 跳过一个冲突值
                f[i] = max(f[i], f[i - 2] + y);
            } else if (i >= 4) {
                // 必然可以接在 f[i-3] 后
                f[i] = max(f[i], f[i - 3] + y);
            }
        }

        return f[n];
    }
};