摘花生

題目來源：《資訊學奧賽一本通》
時間限制：\(1000ms\) 記憶體限制：\(64mb\)

題目描述

Hello Kitty想摘點花生送給她喜歡的米老鼠，
她來到一片有網格狀道路的矩形花生地(如下圖)，從西北角進去，東南角出來，
地里每個道路的交叉點上都有種著一株花生苗，上面有若干顆花生，經過一株花生苗就能摘走該它上面所有的花生，
Hello Kitty只能向東或向南走，不能向西或向北走，
問Hello Kitty最多能夠摘到多少顆花生，
題目描述圖

輸入格式

第一行是一個整數 \(T\) ，代表一共有多少組資料，
接下來是 \(T\) 組資料，
每組資料的第一行是兩個整數，分別代表花生苗的行數 \(R\) 和列數 \(C\) ，
每組資料的接下來 \(R\) 行資料，從北向南依次描述每行花生苗的情況，每行資料有 \(C\) 個整數，按從西向東的順序描述了該行每株花生苗上的花生數目 \(M\) ，

輸出格式

對每組輸入資料，輸出一行，內容為Hello Kitty能摘到得最多的花生顆數，

資料范圍

\(1 ≤ T ≤ 100\) ,
\(1 ≤ R,C ≤ 100\) ,
\(0 ≤ M ≤ 1000\)

樣例輸入

樣例輸出

8
16

解題思路：動態規劃

這類題目用動態規劃的思路來寫，
用一個二維陣列 field 存放給出的 \(R\) 行 \(C\) 列的花生地，
然后用一個二維陣列 dp 記錄從第 \(1\) 行第 \(1\) 列，到第 \(R\) 行第 \(C\) 列的所有方案的最大值，
每一個格子的數為：左和上兩個格子數值較大的一個，再加上本格的花生數，
即：dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + field[i][j]

解題代碼-Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int t = input.nextInt();
        while (t > 0) {
            int row = input.nextInt();
            int col = input.nextInt();
            int[][] field = new int[row + 1][col + 1];

            for (int i = 1; i <= row; i++) {
                for (int j = 1; j <= col; j++) {
                    field[i][j] = input.nextInt();
                }
            }

            int[][] dp = new int[row + 1][col + 1];

            for (int i = 1; i <= row; i++) {
                for (int j = 1; j <= col; j++) {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + field[i][j];
                }
            }

            System.out.println(dp[row][col]);
            t--;
        }
        input.close();
    }
}

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/254353.html

標籤：其他

上一篇：知乎神回復：計算機應屆生月薪大多是多少？10K僅僅才是起薪！

下一篇：業務、設計模式、演算法

2021寒假每日一題《摘花生》

摘花生