LeetCode Daily Problem P3186 Maximum Total Damage from Casting Spells

---

Timeline

Timeline

2025-10-11

init

Sliding window + dynamic programming

---

Problem:

P3186 Maximum Total Damage from Casting Spells

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

Since there may be spells with the same damage, and if multiple spells with the same damage are selected, the total damage should add the damage multiplied by the count of that damage spell. Therefore, we can first save the count of spells for each damage value, and then deduplicate the power.
After deduplicating and sorting the power, let f(i) represent the maximum total damage when selecting from the 0th to the ith type of spell and finally selecting the ith type of spell. The state transition equation can be listed as:

$$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)
        {
                // Let f(i) represent the maximum total damage when selecting from the 0th to the ith type of spell and finally selecting the ith type of spell.
                // 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]++;
                }

                // Deduplicate
                power.erase(std::unique(power.begin(), power.end()), power.end());
                // Sort
                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;
        }
};