class Solution {
public:
long long maximumTotalDamage(vector<int>& power) {
}
};
100316. 施咒的最大总伤害
一个魔法师有许多不同的咒语。
给你一个数组 power ，其中每个元素表示一个咒语的伤害值，可能会有多个咒语有相同的伤害值。
已知魔法师使用伤害值为 power[i] 的咒语时，他们就 不能 使用伤害为 power[i] - 2 ，power[i] - 1 ，power[i] + 1 或者 power[i] + 2 的咒语。
每个咒语最多只能被使用 一次 。
请你返回这个魔法师可以达到的伤害值之和的 最大值 。
示例 1：
输入：power = [1,1,3,4]
输出：6
解释：
可以使用咒语 0，1，3，伤害值分别为 1，1，4，总伤害值为 6 。
示例 2：
输入：power = [7,1,6,6]
输出：13
解释：
可以使用咒语 1，2，3，伤害值分别为 1，6，6，总伤害值为 13 。
提示：
1 <= power.length <= 1051 <= power[i] <= 109原站题解
python3 解法, 执行用时: 782 ms, 内存消耗: 216.9 MB, 提交时间: 2024-06-16 23:18:21
class Solution:
def maximumTotalDamage(self, power: List[int]) -> int:
cnt = Counter(power)
a = sorted(cnt.keys())
@cache
def dfs(i: int) -> int:
if i < 0:
return 0
x = a[i]
j = i
while j and a[j - 1] >= x - 2:
j -= 1
return max(dfs(i - 1), dfs(j - 1) + x * cnt[x])
return dfs(len(a) - 1)
def maximumTotalDamage2(self, power: List[int]) -> int:
cnt = Counter(power)
a = sorted(cnt.keys())
f = [0] * (len(a) + 1)
j = 0
for i, x in enumerate(a):
while a[j] < x - 2:
j += 1
f[i + 1] = max(f[i], f[j] + x * cnt[x])
return f[-1]
java 解法, 执行用时: 141 ms, 内存消耗: 60.3 MB, 提交时间: 2024-06-16 23:17:52
class Solution {
public long maximumTotalDamage(int[] power) {
Map<Integer, Integer> cnt = new HashMap<>();
for (int x : power) {
cnt.merge(x, 1, Integer::sum);
}
int n = cnt.size();
int[] a = new int[n];
int k = 0;
for (int x : cnt.keySet()) {
a[k++] = x;
}
Arrays.sort(a);
long[] f = new long[n + 1];
int j = 0;
for (int i = 0; i < n; i++) {
int x = a[i];
while (a[j] < x - 2) {
j++;
}
f[i + 1] = Math.max(f[i], f[j] + (long) x * cnt.get(x));
}
return f[n];
}
}
java 解法, 执行用时: 193 ms, 内存消耗: 83.7 MB, 提交时间: 2024-06-16 23:17:40
class Solution {
public long maximumTotalDamage(int[] power) {
Map<Integer, Integer> cnt = new HashMap<>();
for (int x : power) {
cnt.merge(x, 1, Integer::sum);
}
int n = cnt.size();
int[] a = new int[n];
int k = 0;
for (int x : cnt.keySet()) {
a[k++] = x;
}
Arrays.sort(a);
long[] memo = new long[n];
Arrays.fill(memo, -1);
return dfs(a, cnt, memo, n - 1);
}
private long dfs(int[] a, Map<Integer, Integer> cnt, long[] memo, int i) {
if (i < 0) {
return 0;
}
if (memo[i] != -1) {
return memo[i];
}
int x = a[i];
int j = i;
while (j > 0 && a[j - 1] >= x - 2) {
j--;
}
return memo[i] = Math.max(dfs(a, cnt, memo, i - 1), dfs(a, cnt, memo, j - 1) + (long) x * cnt.get(x));
}
}
cpp 解法, 执行用时: 463 ms, 内存消耗: 190.5 MB, 提交时间: 2024-06-16 23:17:24
class Solution {
public:
long long maximumTotalDamage(vector<int>& power) {
unordered_map<int, int> cnt;
for (int x : power) {
cnt[x]++;
}
vector<pair<int, int>> a(cnt.begin(), cnt.end());
ranges::sort(a);
int n = a.size();
vector<long long> f(n + 1);
for (int i = 0, j = 0; i < n; i++) {
auto& [x, c] = a[i];
while (a[j].first < x - 2) {
j++;
}
f[i + 1] = max(f[i], f[j] + (long long) x * c);
}
return f[n];
}
// 记忆化搜索
long long maximumTotalDamage2(vector<int>& power) {
unordered_map<int, int> cnt;
for (int x : power) {
cnt[x]++;
}
vector<pair<int, int>> a(cnt.begin(), cnt.end());
ranges::sort(a);
int n = a.size();
vector<long long> memo(n, -1);
auto dfs = [&](auto&& dfs, int i) -> long long {
if (i < 0) {
return 0;
}
long long& res = memo[i]; // 注意这里是引用
if (res != -1) {
return res;
}
auto& [x, c] = a[i];
int j = i;
while (j && a[j - 1].first >= x - 2) {
j--;
}
return res = max(dfs(dfs, i - 1), dfs(dfs, j - 1) + (long long) x * c);
};
return dfs(dfs, n - 1);
}
};
golang 解法, 执行用时: 302 ms, 内存消耗: 13.1 MB, 提交时间: 2024-06-16 23:16:45
func maximumTotalDamage(power []int) int64 {
cnt := map[int]int{}
for _, x := range power {
cnt[x]++
}
n := len(cnt)
a := make([]int, 0, n)
for x := range cnt {
a = append(a, x)
}
slices.Sort(a)
f := make([]int, n+1)
j := 0
for i, x := range a {
for a[j] < x-2 {
j++
}
f[i+1] = max(f[i], f[j]+x*cnt[x])
}
return int64(f[n])
}
golang 解法, 执行用时: 355 ms, 内存消耗: 34 MB, 提交时间: 2024-06-16 23:16:29
// 值域打家劫舍 + 记忆化搜索
func maximumTotalDamage(power []int) int64 {
cnt := map[int]int{}
for _, x := range power {
cnt[x]++
}
n := len(cnt)
a := make([]int, 0, n)
for x := range cnt {
a = append(a, x)
}
slices.Sort(a)
memo := make([]int, n)
for i := range memo {
memo[i] = -1
}
var dfs func(int) int
dfs = func(i int) int {
if i < 0 {
return 0
}
p := &memo[i]
if *p != -1 {
return *p
}
x := a[i]
j := i
for j > 0 && a[j-1] >= x-2 {
j--
}
*p = max(dfs(i-1), dfs(j-1)+x*cnt[x])
return *p
}
return int64(dfs(n - 1))
}