3186. 施咒的最大總傷害

思路

根據力量大小排序好法術之後，定義f[i]代表選擇前i個法術的最佳選擇，

1. 使用一個力量為p的法術之後，就不能用其他力量相近的法術（跟p力量相差2以下），
2. 如果選擇使用這個法術，把所有力量p的法術都用掉是最好的。
3. 對於每一個法術，我們都能選或不選擇使用它。

依據前三點，能分為兩種情況討論。

• 選擇當前法術，令power[j]是在power[i]之前的最大可用法術，f[i] = f[j] + power[i] * 力量p的法術數量。
• 不選擇當前法術，f[i] = f[i - 1]

程式碼

1. 記憶化搜索

class Solution {
public:
    long long maximumTotalDamage(vector<int>& power) {
        unordered_map<int, int> freq; // 法術的出現次數
        for(int x : power) ++freq[x];
        vector<pair<int,int>> nums(freq.begin(), freq.end()); // 法術, 出現次數
        ranges::sort(nums);
        int n = nums.size();
        vector<long long> memo(n, -1);
        auto dfs = [&](this auto&&dfs, int i) -> long long { // dfs(i) 代表前 i 個法術的最佳選擇
            if(i < 0) return 0;
            long long& res = memo[i];
            if(res != -1) return res;
            auto& [x, c] = nums[i]; // 法術，出現次數
            int j = i;
            // 選擇使用法術(power = x)，力量在 x - 2 ~ x 之間的法術都不能用
            // 需要找到對應的位置
            while(j && nums[j - 1].first >= x - 2) {
                --j;
            }
            // 不選擇使用法術，相當於 dfs(i - 1)
            return res = max(dfs(i - 1), dfs(j - 1) + 1LL * x * c);
        };
        return dfs(n - 1);
    }
};

2.轉換成遞推

class Solution {
public:
    long long maximumTotalDamage(vector<int>& power) {
        unordered_map<int, int> freq; // 法術的出現次數
        for(int x : power) ++freq[x];
        vector<pair<int,int>> nums(freq.begin(), freq.end()); // 法術, 出現次數
        ranges::sort(nums);
        int n = nums.size();
        vector<long long> f(n + 1);
        for(int i = 0, j = 0; i < n; ++i) {
            auto& [x, c] = nums[i];
            while(nums[j].first < x - 2) {
                ++j;
            }
            f[i + 1] = max(f[i], f[j] + 1LL * x * c);
        }
        return f[n];
    }
};

複雜度分析

• 時間複雜度：$O(n\log{n})$
• 空間複雜度：$O(n)$