2140. Solving Questions With Brainpower

周賽復盤,

這題比較可惜, 最後其實有想出來, 但睡太晚了ＸＤ

直覺第一眼本來是要用bfs, 但是他的長度為10⁵

一定要在O(n²)以下解決,

後來想到用dp

一開始我先這麼想

先選下question(A)後, 用一個map記載他下一個順位question(B)可以參考的分數總癟, 因為B很有可能有很多候選人, 所以我用一個priority去記載所有人後選最高分的哪個
然後就小小卡關了, 原來是Question可以選擇不要回答, 但是你當前的最高分必須傳給下一個人即使你不回答(有那種很雷的case就是你選了小分數他給你卡超多questions掉)
所以你必須把當前不加上自己的最高分往下傳

看完上述的分析, 我們就可以開始來寫code了

class Solution {
public:
    long long mostPoints(vector<vector<int>>& qts) {
        vector<long long> dp(qts.size(), 0);
        unordered_map<long long , priority_queue<long long, vector<long long>, less<long long>>> st;
        long long res = 0;
        for(int i = 0; i < qts.size();i++){
           
            if(!st[i].empty()){
                dp[i] += st[i].top();
            }
            
            res = max(res, dp[i] + qts[i][0]);
            
            st[i + qts[i][1] + 1].push({dp[i]+ qts[i][0]});
            st[i + 1].push({dp[i]});
            
        }
        return res;
        
        
    }
};

時間複雜度為O(nlogn)

後來我發現我們無需用priority去記載, 我只要留下最高分的那個數字即可,

這樣時間複雜度即可為O(n)

class Solution {
public:
    long long mostPoints(vector<vector<int>>& qts) {
        vector<long long> dp(qts.size(), 0);
        unordered_map<long long , long long> st;
        long long res = 0;
        for(int i = 0; i < qts.size();i++){
           
            if(st.count(i)){
                dp[i] += st[i];
            }
            
            res = max(res, dp[i] + qts[i][0]);
if(st.count(i + qts[i][1] + 1)){
                st[i + qts[i][1] + 1] = max(dp[i]+ qts[i][0],  st[i + qts[i][1] + 1]) ;
            }else{
                st[i + qts[i][1] + 1] = dp[i]+ qts[i][0];
            }
            if(st.count(i + 1)){
                st[i + 1] = max(st[i + 1], dp[i]);
            }else{
                st[i + 1] = dp[i];
            }
           
            
        }
        return res;
        
        
    }
};