Re: [閒聊] 每日LeetCode

[oin1104 (是oin的說)]

※ 引述 《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: 停止內捲
推 Che31128: 大師 差點炸掉：）
→ oin1104: 什麼東西炸掉 你的蛋蛋嗎 我幫你含住
→ XROCK: 臭甲 幹
→ oin1104: 我開個玩笑 大過年的 不要這麼嚴肅
推 sustainer123: 大師
推 SecondRun: 捲狗
→ oin1104: 哥們 我已經讀學店了 再不捲我真的要吃土了
推 XROCK: 東華什麼時候也學店了
→ oin1104: 庭庭清華 魯肥台大 泥板隨便抓一個都四大四中 只剩我國
→ oin1104: 立底邊了
推 JIWP: 學霸
→ JIWP: 剩我沒在寫每日了
推 sustainer123: 學霸
→ sustainer123: 我最近又開始刷75
→ JIWP: 別捲了
推 temsroluan: 雪霸
→ RinNoKareshi: 學霸
→ sc95819200: 你板剩我是廢物了