Acwing1015. 摘花生

本文主要是介绍Acwing1015. 摘花生，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Hello Kitty想摘点花生送给她喜欢的米老鼠。
她来到一片有网格状道路的矩形花生地(如下图)，从西北角进去，东南角出来。
地里每个道路的交叉点上都有种着一株花生苗，上面有若干颗花生，经过一株花生苗就能摘走该它上面所有的花生。
Hello Kitty只能向东或向南走，不能向西或向北走。
问Hello Kitty最多能够摘到多少颗花生。

输入格式

第一行是一个整数T，代表一共有多少组数据。
接下来是T组数据。
每组数据的第一行是两个整数，分别代表花生苗的行数R和列数 C。
每组数据的接下来R行数据，从北向南依次描述每行花生苗的情况。每行数据有C个整数，按从西向东的顺序描述了该行每株花生苗上的花生数目M。

输出格式

对每组输入数据，输出一行，内容为Hello Kitty能摘到得最多的花生颗数。
数据范围
$1\le T\le 100$,
$1\le R,C\le 100$,
$0\le M\le 1000$

---

注意：在平时解决数学问题时，直角坐标系通常是x轴指向右侧，y轴指向上方；但是在算法题目中一旦出现直角坐标系，通常是x轴指向右侧，y轴指向下方。

---

本题目使用动态规划法进行求解，通过闫氏DP分析法进行分析：
状态表示：f[i][j]

• 集合：从（0，0）走到（i，j）的所有的路径所取得的花生数目。
• 属性：MAX

状态计算：以最后一步的之前一步进行分割–>分为从左来和从上来；

• 状态方程：f[i, j] = max(f[i-1, j], f[i, j-1]) + w[i, j]

代码：

java运行本题时，Scanner会超时，这里我们将使用BufferReader，速度将会有极大的提升。

import java.io.*;
import java.util.*;public class Main {public static void main(String[] args) throws Exception {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));int T = Integer.parseInt(br.readLine());while(T -- > 0) {String[] arr = br.readLine().split(" ");int row = Integer.parseInt(arr[0]);int col = Integer.parseInt(arr[1]);int [][]a = new int[row+2][col+2];for(int i = 1; i <= row; ++i) {String[] ar = br.readLine().split(" ");for(int j = 1; j <= col; ++j) {a[i][j] = Integer.parseInt(ar[j-1]);}}int [][]dp = new int[row+2][col+2];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])+a[i][j];}}System.out.println(dp[row][col]);}}}

做完了

这篇关于Acwing1015. 摘花生的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---