题目描述
小蓝在一个n行m列的方格图中玩一个游戏。
开始时,小蓝站在方格图的左上角,即第1行第1列。
小蓝可以在方格图上走动,走动时,如果当前在第r 行第 c 列,他不能走到行号比 r 小的行,也不能走到列号比 c 小的列。同时,他一步走的直线距离不超过 3。
例如,如果当前小蓝在第 33 行第 55 列,他下一步可以走到第 3 行第 6 列、第 3 行第 7 列、第 3 行第 8 列、第 4 行第 5 列、第 4 行第 6 列、第 4 行第 7 列、第 5 行第 5 列、第 5 行第 6 列、第 6 行第 5 列之一。
小蓝最终要走到第 n 行第 m 列。
在图中,有的位置有奖励,走上去即可获得,有的位置有惩罚,走上去就要接受惩罚。奖励和惩罚最终抽象成一个权值,奖励为正,惩罚为负。
小蓝希望,从第 1 行第 1 列走到第 n 行第 m 列后,总的权值和最大。请问最大是多少?
输入描述
输入的第一行包含两个整数 n, mn,m,表示图的大小。
接下来 nn 行,每行 mm 个整数,表示方格图中每个点的权值。
其中, 10^4≤n≤100,−10^4≤权值≤10^4。
import java.util.Scanner; // 1:无需package // 2: 类名必须Main, 不可修改 public class Main { public static void main(String[] args) { Scanner scan = new Scanner(System.in); int a=scan.nextInt(); int b=scan.nextInt(); int[][] arr=new int[a][b]; for(int i=0;i<a;i++){ for(int j=0;j<b;j++){ arr[i][j]=scan.nextInt(); } } //路径寻找 ———— 通过二维数组进行路径权值的填充 int[][] dp=new int[a][b]; for(int i=0;i<a;i++){ for(int j=0;j<b;j++){ dp[i][j]=-1000000; //设置起始最小值 —— 小于-10^4 for(int k=i;k>=0 && i-k<=3;k--){ // k>=0 二维数组范围 i-k<=3 只能挑动三格 for(int l=j;l>=0 && (i-k-l+j<=3);l--){ dp[i][j]=Math.max(dp[i][j],dp[k][l]+arr[i][j]); } } if(i==0&&j==0) dp[i][j]=arr[i][j]; } } System.out.println(dp[a-1][b-1]); } }
import java.util.Scanner; // 1:无需package // 2: 类名必须Main, 不可修改 public class Main { public static void main(String[] args) { Scanner scan = new Scanner(System.in); int a=scan.nextInt(); int b=scan.nextInt(); int[][] arr=new int[a][b]; for(int i=0;i<a;i++){ for(int j=0;j<b;j++){ arr[i][j]=scan.nextInt(); } } //路径寻找 ———— 通过二维数组进行路径权值的填充 int[][] dp=new int[a][b]; for(int i=0;i<a;i++){ for(int j=0;j<b;j++){ dp[i][j]=-1000000; //设置起始最小值 —— 小于-10^4 for(int k=i;k>=0 && i-k<=3;k--){ // k>=0 二维数组范围 i-k<=3 只能挑动三格 for(int l=j;l>=0 && (i-k-l+j<=3);l--){ dp[i][j]=Math.max(dp[i][j],dp[k][l]+arr[i][j]); } } if(i==0&&j==0) dp[i][j]=arr[i][j]; } } System.out.println(dp[a-1][b-1]); } } 标签:java,Scanner,scan,int,行第,路径,&&,跳跃,dp From: https://www.cnblogs.com/mcpf/p/17035137.html