Weekly Contest 402

日期 2024/06/16
這次只有作到第二題，第三題可以看出是 Dynamic Programming，但是無從下手。

• Count Pairs That Form a Complete Day I
• Count Pairs That Form a Complete Day II
• Maximum Total Damage With Spell Casting
• Peaks in Array

第一題

int countCompleteDayPairs(vector<int>& hours) {
    const int n = hours.size();
    int ret = 0;
    for(int i = 0; i < n; i++) {
        for(int j = i + 1; j < n; j++) {
            ret += (hours[i] + hours[j]) % 24 == 0;
        }
    }
    return ret;
}

第二題

long long countCompleteDayPairs(vector<int>& hours) {
    const int n = hours.size();
    vector<long long> mm(24, 0);
    for(int h: hours) {
        int x = h % 24;
        mm[x]++;
    }

    long long ret = 0;
    ret += mm[0] * (mm[0] - 1) / 2;
    ret += mm[12] * (mm[12] - 1) / 2;

    for(int i = 1; i < 12; i++) {
        int x = mm[i] * mm[24 - i];
        ret += x;
    }
    return ret;
}

第三題

這題很多人 TLE，即使寫法上看起沒問題。
本題 hourse robbing 題目相同。

TLE 版本

class Solution {
public:
    using ll = long long;

    map<int, ll> freq;
    vector<int> uniquePower;
    vector<ll> dp;
    long long maximumTotalDamage(vector<int>& power) {
        sort(power.begin(), power.end());
        for (int x : power)
            freq[x]++;
        for (auto it : freq)
            uniquePower.push_back(it.first);
        dp = vector<ll>(uniquePower.size(), -1);
        return solve(0);
    }

    ll solve(int start) {
        const int n = uniquePower.size();
        if(start >= n)
            return 0;
        if(dp[start] != -1)
            return dp[start];
        // dp[i] --> 以 [i..< n] 最大傷害
        // 沒取
        ll notTake = solve(start + 1);

        // 取
        auto it = upper_bound(uniquePower.begin(), uniquePower.end(), uniquePower[start] + 2);
        int index = it - uniquePower.begin();
        int x = uniquePower[start];
        ll take = solve(index) + freq[x] * x;
        dp[start] = max(take, notTake);
        return dp[start];
    }
};

Accept 版本

參考討論區

using ll = long long;
long long maximumTotalDamage(vector<int>& power) {
    const int n = power.size();
    sort(power.begin(), power.end());
    vector<ll> dp(power.size() + 1, 0);
    ll max_dp = 0;
    int i = 0;
    int j = 0;
    while(i < n) {
        if(power[i] == power[max(0, i - 1)])
            dp[i + 1] = power[i] + dp[i];
        else {
            while(power[j] + 2 < power[i]) {
                j++;
                max_dp = max(max_dp, dp[j]);
            }
            dp[i + 1] = power[i] + max_dp;
        }
        i++;
    }
    return *max_element(dp.begin(), dp.end());
}

Best 版本

參考 Submission 內容

using ll = long long;
long long maximumTotalDamage(vector<int> &power)
{
    map<int, ll> c;
    for (int x : power)
        c[x] += x;

    // 不取、取
    ll dp[2] = {0, -1};
    ll last = -1;
    for (auto &p : c) {
        ll d1 = max(dp[0], dp[1]);

        ll d2;
        if (last < p.first - 1) {
            d2 = dp[1];
        } else {
            d2 = -1;
        }
        d2 = max(dp[0], d2);
        d2 = max(0LL, d2);

        dp[0] = d1;
        dp[1] = d2 + p.second;
        last = p.first;
    }
    return max(dp[0], dp[1]);
}

第四題