3186-施咒的最大傷害

思路

題目大意是：選出一個子集，這個子集需要滿足一個要求：子集中元素相互之間的差值不能是1和2，目標求最大子集和

• 直接考慮一個元素應不應該被選上既要考慮比它小的，又要考慮比它大的，比較麻煩，我們直接從小往大考慮，加入一個數的時候就只用考慮比它小的數就可以了，所以我們先把數組排個序

• 接著我們考慮每一個元素，對于元素\(a_i\)，如果\(a_{i - 1} = a_i\)，那么\(a_i\)肯定跟在\(a_{i - 1}\)的后面才能保證此時是在選上\(a_{i}\)的情況下的最優解

• 如果\(a_{i - 1} \neq a_{i}\)，此時我們在一個合法范圍內\((a_i - a_j \geq 3)\)時找一個最大值就好，因為我們已經提前排過序了，所以此時可用用二分查找, 找最大值就理所當然地維護一個前綴最大值就好了

那么這個題目我們就維護兩個數組就好了
\(premax[i]\) : 前\(i\)個元素取值的最大值
\(dp[i]\) : 前\(i\)個元素，選上元素\(i\)時的最大值

代碼

using lli = long long;
class Solution {
public:
    lli maximumTotalDamage(std::vector<int>& power) 
    {
        int n = power.size();
        std::vector<lli> premax(n, 0);
        std::vector<lli> dp(n, 0);
        std::sort(power.begin(), power.end());
        dp[0] = power[0];
        premax[0] = dp[0];
        for (int i = 1; i < n; i++)
        {
            if (power[i] == power[i - 1])
            {
                dp[i] = dp[i - 1] + power[i];
            }
            else
            {
                int l = -1, r = i;
                while(l + 1 < r)
                {
                    int mid = (l + r) >> 1;
                    if (power[i] - power[mid] >= 3)
                    {
                        l = mid;
                    }
                    else
                    {
                        r = mid;
                    }
                }
                if (l == -1)
                {
                    dp[i] = power[i];
                }
                else
                {
                    dp[i] = premax[l] + power[i];
                }
            }
            premax[i] = std::max(premax[i - 1], dp[i]);
        }
        lli ans = 0;
        for (int i = 0; i < n; i++) ans = std::max(ans, dp[i]);
        return ans;
    }
};