本文涉及的基础知识点

下载及打开打包代码的方法兼述单元测试
C++算法：前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频
C++动态规划

LeetCode3186. 施咒的最大总伤害

一个魔法师有许多不同的咒语。
给你一个数组 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 <= 10⁵
1 <= power[i] <= 10⁹

排序+动态规划+双指针

能否选取和值有关，和下标无关，故排序不影响结果。有序映射mCnt记录各值的数量。

动态规划的状态表示

dp[i] 选取的咒语最大伤害为i的方案的最大总伤害。O(n)。

动态规划的转移方程

{ d p [ i ] = i × m C n t [ i ] 只选取一种咒语 d p [ i ] = i × m C n t [ i ] + m a x ( d p [ j ] ) j < i − 2 \begin{cases} dp[i] = i \times mCnt[i] && 只选取一种咒语 \\ dp[i] = i \times mCnt[i] +max(dp[j]) j <i-2 \\ \end{cases} {dp[i]=i×mCnt[i]dp[i]=i×mCnt[i]+max(dp[j])j<i−2​只选取一种咒语
iMax 记录max(dp[j])的最大值，这样总复杂度是：O(n)

动态规划的初始化

dp和mCnt为空。

动态规划的填表顺序

for( [i,cnt] : mCnt

动态规划的返回值

dp.back()
i1 < i2，则dp[i1]必定小于dp[i2] 。将i1方案的i1换成i2，更优。错误原因： i1可能有多个。
所以还是需要枚举。

代码

核心代码

	class Solution {
		public:
			long long maximumTotalDamage(vector<int>& power) {
				map<int, int> mCnt;
				unordered_map<int,long long >dp;
				for (const auto& i : power) {
					mCnt[i]++;
				}
				auto it = mCnt.begin();
				long long iMax = 0;
				long long ans = 0;
				for (const auto& [i, cnt] : mCnt) {
					while ((it != mCnt.end()) && (it->first < i - 2)) {
						iMax = max(iMax,dp[it->first]); it++;
					}
					dp[i] = iMax + (long long)i* cnt;
					ans = max(ans, dp[i]);
				}
				return ans;
			}
		};

单元测试

vector<int> power;
		TEST_METHOD(TestMethod11)
		{
			power = { 1, 1, 3, 4 };
			auto res = Solution().maximumTotalDamage(power);
			AssertEx(6LL, res);
		}
		TEST_METHOD(TestMethod12)
		{
			power = { 7,1,6,6 };
			auto res = Solution().maximumTotalDamage(power);
			AssertEx(13LL, res);
		}