leetcode 3186. 施咒的最大总伤害

6个月前更新

150

3186. 施咒的最大总伤害

这道题相比 740. 删除并获得点数，区别是这道题的元素值可以特别大，所以就不能开大数组。

没做出来🤡

class Solution { public: //定义 dfs(i) 表示从 a[0] 到 a[i] 中选择，可以得到的伤害值之和的最大值。 //不选：问题变成从 a[0] 到 a[i−1] 中选择，可以得到的伤害值之和的最大值，即 dfs(i)=dfs(i−1)。 //选：那么伤害值等于 a[i]−2 和 a[i]−1 的数不能选，问题变成从 a[0] 到 a[j−1] 中选择，可以得到的伤害值之和的最大值， //其中 j 是最小的满足 a[j]≥a[i]−2 的数。那么 dfs(i)=dfs(j−1)+a[i]⋅cnt[a[i]]。 //两种情况取最大值，得 dfs(i)=max(dfs(i−1),dfs(j−1)+a[i]⋅cnt[a[i]])

    long long maximumTotalDamage(vector<int>& power) { unordered_map<int,int> cnt; for(int &p : power)  ++cnt[p]; vector<pair<int,int>> a(cnt.begin(),cnt.end()); ranges::sort(a); int n = a.size(); // 使用动态规划的记忆化数组，初始化为-1表示未计算
        vector<long long> memo(n, -1); // 定义一个递归函数来计算最大总伤害
        auto dfs = [&](auto&& dfs, int i) -> long long{ // 基本情况：当i < 0时，没有攻击力可以选择，返回0
            if (i < 0)  return 0; // 如果memo[i]已经计算过，则直接返回结果，避免重复计算
            if (memo[i] != -1)  return memo[i]; // 获取当前攻击力和出现次数 //a[i] 是一个 std::pair<int, int> 类型的元素，其中 a 是一个存储了多个 std::pair<int, int> 的向量。 //每个 pair 包含两个整数：第一个整数是攻击力，第二个整数是该攻击力在输入数组中出现的次数。 //auto& [x, c] 是一个结构化绑定的声明，它创建了两个引用变量 x 和 c。这两个变量分别引用了 a[i] 中的第一个和第二个元素。 //使用 auto& 而不是 auto 是为了确保 x 和 c 是对 a[i] 中元素的引用，而不是它们的拷贝。 //这意味着，如果通过 x 或 c 修改了值，那么 a[i] 中的相应元素也会被修改。 //在这个例子中，结构化绑定使得我们可以轻松地访问 a[i] 中的攻击力（x）和出现次数（c），而无需使用类似 a[i].first 和 a[i].second 的语法。 //代码 auto& [x, c] = a[i]; 是 C++17 引入的结构化绑定（structured binding）语法的一个例子。这个语法允许你从一个可以分解为多个元素的实体（如std::pair、std::tuple、结构体、数组等）中同时提取多个值，并将它们分别绑定到不同的变量上。
            auto& [x, c] = a[i]; // 找到可以连续使用的攻击力的最远索引j，即a[j].first >= x - 2
            int j = i; while (j > 0 && a[j - 1].first >= x - 2) { j--; } // 计算两种情况下的最大伤害：不使用当前攻击力，或者使用当前攻击力并考虑连续使用的伤害 // 将计算结果存储到memo[i]中，并返回
            return memo[i] = max(dfs(dfs, i - 1), dfs(dfs, j - 1) + (long long) x * c); }; // 调用递归函数，从最后一个攻击力开始计算最大总伤害
        return dfs(dfs,n - 1); } };