时间轴

2025-10-11

init

题目：

P3186 施咒的最大总伤害

https://leetcode.cn/problems/maximum-total-damage-with-spell-casting/description/?envType=daily-question&envId=2025-10-11

由于可能存在相同伤害的咒语，而如果选择了有多个同伤害的咒语，那么总伤害要加上该伤害*该伤害咒语的数量。因此我们可以先保存每个伤害值的咒语数量，然后将 power 去重。
将 power 去重排序后，令 f(i) 表示从第 0 到 i 种咒语中选择，并且最后选择第 i 种咒语的最大总伤害，可列出状态转移方程：

$$
f[i] = \text{power}[i] + \max_{0\le j < i, , power[j] \le power[i] - 2} f[j]
$$

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
#include <algorithm>
#include <unordered_map>
#include <vector>

using std::unordered_map;
using std::vector;

class Solution {
public:
  long long maximumTotalDamage(vector<int> &power) {
    // 令 f(i) 表示从第 0 到 i 种咒语中选择，并且最后选择第 i 种咒语的最大总伤害
    // f(i) = max(f(j), j< i && power[j] < power[i]-2) + power[i] * mp[power[i]]
    int i, j, n;
    long long max = 0, ans = 0;
    unordered_map<long, long> count;

    for (int p : power) {
      count[p]++;
    }

    // 去重
    power.erase(std::unique(power.begin(), power.end()), power.end());
    // 排序
    std::sort(power.begin(), power.end());

    n = power.size();

    vector<long long> f(n, 0);
    f[0] = power[0] * count[power[0]];

    for (i = 1, j = 0; i < n; i++) {
      while (j < i && power[j] < power[i] - 2) {
        max = std::max(max, f[j]);
        j++;
      }
      f[i] = max + power[i] * count[power[i]];
    }

    ans = *std::max_element(f.begin(), f.end());

    return ans;
  }
};