Re: [閒聊] 每日leetcode

看板Marginalman作者sixB (6B)時間1年前 (2024/08/21 08:34)推噓0(1推 1噓 2→)

留言4則, 3人參與討論串745/1548 (看更多)

1140. 昨天的我打雀魂一整個晚上哇啊啊啊啊新模式好好玩嗚嗚嗚嗚思路: 一開始想說兩個人那我開兩個dp讓他們take turn去記 prefix加完發現不對我現在這格dp算的就是這次拿的+剩下的全部 - 下一格dp 因為兩個人輪流拿 presum 改sufsum dp開一個紀錄在<idx, m>的人可以拿到的最多石頭跑好慢99ms 醒來再看solution都怎麼寫還有今天ㄉ題== class Solution { public: int stoneGameII(vector<int>& piles) { int n = piles.size(); //suffix sum for(int i = n-2; i >= 0 ; i--){ piles[i] += piles[i+1]; } int m = 1; map <pair<int, int>, int> dp; return play(piles, dp, 0, 1); //<idx, x> } int play(vector<int>& piles, map<pair<int, int>, int>& dp, int idx, int m){ //for(x = 1 ... 2m) //dp[{idx, x}] = max(dp[], piles[idx] - piles[idx + x] + (piles[idx + x] - play())); //dp[{idx, m}] = max(dp[{idx, m}], piles[idx] - play(piles, dp, idx + x, max(x, m))); if(dp.find({idx, m}) != dp.end()){ return dp[{idx, m}]; } dp[{idx, m}] = 0; if(idx + m*2 >= piles.size()){ //take all dp[{idx, m}] = piles[idx]; return dp[{idx, m}]; } for(int x = 1; x <= m * 2; x++){ dp[{idx, m}] = max(dp[{idx, m}], piles[idx] - play(piles, dp, idx + x, max(x, m))); } return dp[{idx, m}]; } }; ----- Sent from JPTT on my iPad -- 很姆的咪姆之咪 http://i.imgur.com/5sw7QOj.jpg