施法造成的最大总伤害
Maximum Total Damage With Spell Casting
题目详情
问题：施法造成的最大总伤害
考察：动态规划、数组、贪心
来源：Citadel
链接：https://www.jointaro.com/interviews/questions/maximum-total-damage-with-spell-casting/
A magician has various spells.
You are given an array power, where each element represents the damage of a spell. Multiple spells can have the same damage value.
It is a known fact that if a magician decides to cast a spell with a damage of power[i], they cannot cast any spell with a damage of power[i] - 2, power[i] - 1, power[i] + 1, or power[i] + 2.
Each spell can be cast only once.
Return the maximum possible total damage that a magician can cast.
Example 1:
Input: power = [1,1,3,4]
Output: 6
Explanation:
The maximum possible damage of 6 is produced by casting spells 0, 1, 3 with damage 1, 1, 4.
Example 2:
Input: power = [7,1,6,6]
Output: 13
Explanation:
The maximum possible damage of 13 is produced by casting spells 1, 2, 3 with damage 1, 6, 6.
Constraints:
1 <= power.length <= 1051 <= power[i] <= 109
解析
思路：先按伤害值合并相同法术的总贡献，再在有序伤害值上做类似 Delete and Earn 的 DP。选择某个伤害值时跳过与它冲突的相邻伤害范围。
复杂度：排序 O(n log n)，DP O(u)，空间 O(u)。