→ Rushia: 你好優秀 04/01 23:10
推 JIWP: 大師，我好崇拜你 04/01 23:10
→ sixB: 醜死了幹== 04/01 23:12
2140.
有點像搶房子
不過每間有規定搶了之後要跳過幾格
一開始只開3格dp
後來發現沒辦法
他不是固定跳過一個
我就想ㄚ
這間搶了 那這個值要跳到哪邊才能再取
直接把他擺到後面去 能用的時候再管他
##
dp[i] 不是第i格最大
是我現在還沒取i 並且可以取iㄉ最大
所以第i格最大是dp[i] + point[i]
##
using ll = long long;
class Solution {
public:
long long mostPoints(vector<vector<int>>& q) {
// rob house
int n = q.size();
vector<ll> dp(n, 0);
ll cur_mx = 0, mx = 0;
for(int i = 0; i < n; i++){
cur_mx = max(cur_mx, dp[i]);
dp[i] = cur_mx;
ll p = q[i][0] + dp[i], offset = q[i][1] + 1;
mx = max(mx, p);
if(i + offset < n){
dp[i + offset] = max(p, dp[i + offset]);
}
}
return mx;
}
};
一遍過ㄟ連分號都沒有忘記直接ac
我真的好厲害><
solution每個都倒著做好怪
感覺都gpt
愛了
想叫gpt幫我把扣轉成吉卜力風格
--
很姆的咪
姆之咪
http://i.imgur.com/5sw7QOj.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.205.121.194 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1743519918.A.BB0.html