Re: [閒聊] 每日LeetCode

看板Marginalman作者oin1104 (是oin的說)時間4月前 (2024/02/11 22:31)推噓6(7推 1噓 11→)

留言19則, 10人參與討論串671/719 (看更多)

※ 引述《JIWP (神楽めあ的錢包)》之銘言： : 　 : 1463 Cherry Pickup II : 　 : 給一個2維矩陣grid，grid[i][j]代表這個格子的櫻桃數量 : 　 : 有兩個機器人會收集格子上的櫻桃 : 　 : 當兩個機器人走到同一格的時候，只有一個機器人可以拿grid[i][j]個櫻桃，另一個拿0 個 : 　 : 機器人一個是從左上角grid[0][0]，另一個是從右上角grid[0][cols-1] : 　 : 每次可以往左下、正下、右下走 : 　 : 請問機器人最多可以收集幾個櫻桃這題一開始蠻難想的偷偷看了一下提示之後哇幹對欸可以三維姆咪思路：有圖應該就很好懂ㄌ https://i.imgur.com/nstwFsh.jpg

就跟下墜一樣要把每一層的動作分開來討論然後要先知道某一層地方每一種走法的sum 所以會用paper來記錄他們接下來就可以dp了每一層都用sum來記錄走過的總和然後兩個機器人都可以左右一格所以sum在更新的時候要看自己的九宮格最大的然後最後再看最後一層最大的就可以了我beat 99.??% 媽的好爽 class Solution { public: int cherryPickup(vector<vector<int>>& grid) { int layer = grid.size(); int n = grid[0].size(); int paper[layer][n][n]; int sum[layer][n][n]; for(int l = 0 ; l < layer ; l ++) { for(int i = 0 ; i < n ; i ++) { for(int j = 0 ; j < n ; j ++) { if(i != j) { paper[l][i][j] = grid[l][i] + grid[l][j]; } else if(i == j) { paper[l][i][j] = grid[l][i]; } sum[l][i][j] = -1; } } } sum[0][n-1][0] = paper[0][n-1][0]; for(int l = 1 ; l < layer ; l ++) { for(int i = 0 ; i < n ; i ++) { for(int j = 0 ; j < n ; j ++) { int lastmax = -1; if((i-1>=0)&&(j-1>=0)) { lastmax = max(lastmax , sum[l-1][i-1][j-1]); } if((i-1>=0)) { lastmax = max(lastmax , sum[l-1][i-1][j]); } if((i-1>=0)&&(j+1<n)) { lastmax = max(lastmax , sum[l-1][i-1][j+1]); } if((j-1>=0)) { lastmax = max(lastmax , sum[l-1][i][j-1]); } lastmax = max(lastmax , sum[l-1][i][j]); if(j+1<n) { lastmax = max(lastmax , sum[l-1][i][j+1]); } if((i+1<n)&&(j-1>=0)) { lastmax = max(lastmax , sum[l-1][i+1][j-1]); } if((i+1<n)) { lastmax = max(lastmax , sum[l-1][i+1][j]); } if((i+1<n)&&(j+1<n)) { lastmax = max(lastmax , sum[l-1][i+1][j+1]); } if(lastmax!=-1) { sum[l][i][j] = lastmax + paper[l][i][j]; } } } } int ans = 0; for(int i = 0 ; i < n ; i ++) { for(int j = 0 ; j < n ; j ++) { ans = max(sum[layer-1][i][j] , ans); } } return ans; } }; -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.162.28.91 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1707661899.A.FD4.html

噓

wu10200512

02/11 22:34, 4月前 , 1^F

02/11 22:34, 1^F

推

Che31128

02/11 22:35, 4月前 , 2^F

02/11 22:35, 2^F

→

oin1104

02/11 22:36, 4月前 , 3^F

02/11 22:36, 3^F