噓 LabMumi: 很六的逼08/21 08:39
很拉的姆咪
→ sixB: map改vector08/21 08:39
→ sixB: recursive改iterative 這個應該差不多08/21 08:39
※ 編輯: sixB (123.205.121.194 臺灣), 08/21/2024 08:40:41
推 XXXXROA: 為啥你要偷阿芬簽名檔 08/21 08:46
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
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.205.121.194 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1724200475.A.887.html