leetcode每日一题 P3186 施咒的最大总伤害

---

时间轴

时间轴

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]$$

#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;
        }
};