尋寶路線 (40 point(s))

在一個m行n列方格矩陣中，每一個方格內(nèi)擺放著價值不等的寶貝（價值可正可負），讓小明感到好奇的是，從左上角到達右下角的所有可能路線中，能撿到寶貝的價值總和最大是多少？而且這種達到最大值的路線 又有多少條？【注意：只能從一個格子向下或向右走到相鄰格子，并且走到的格子寶貝一定會被撿起。】

輸入格式:

第一行為整數(shù)m，n（均不大于100）， 下一行開始會有一個m行n列的整數(shù)方陣， 對應(yīng)方格矩陣中的寶貝價值（這些值的絕對值都不超過500）。

輸出格式:

單獨一行輸出2個整數(shù)， 分別為能撿到寶貝價值總和的最大值和達到最大值的路線數(shù)量， 2個整數(shù)間隔一個空格。

輸入樣例:

在這里給出一組輸入。例如：

4 5 2 -1 6 -2 9 -3 2 5 -5 1 5 8 3 -2 4 5 2 8 -4 7

輸出樣例:
對應(yīng)的輸出為：

26 3

java dfs

import java.io.*; import java.util.*;public class Main {public static void main(String[] args) {Scanner in = new Scanner(new BufferedInputStream(System.in));m = in.nextInt();n = in.nextInt();int[][] a = new int[m][n];for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {a[i][j] = in.nextInt();}}in.close();dfs(a, 0, 0, 0);Integer max = Collections.max(map.keySet());System.out.println(max + " " + map.get(max));}static int m = 0, n = 0;static HashMap<Integer, Integer> map = new HashMap<>();private static void dfs(int[][] a, int i, int j, int q) {if (i == a.length - 1 && j == a[0].length - 1) {q += a[m - 1][n - 1];map.put(q, map.getOrDefault(q, 0) + 1);q -= a[m - 1][n - 1];return;}if (i == m - 1) {dfs(a, i, j + 1, q + a[i][j]);} else if (j == n - 1) {dfs(a, i + 1, j, q + a[i][j]);} else {dfs(a, i + 1, j, q + a[i][j]);dfs(a, i, j + 1, q + a[i][j]);}}}

動態(tài)規(guī)劃

import java.io.*; import java.util.*;// import algorithms.Util;public class Main {static int[][] dp;static int[][] a;static int[][] dir = { { 0, -1 }, { -1, 0 } };static int ans = 0;static int m, n;static void dfs(int sum, int row, int col) {if (sum == a[1][1]) {ans++;return;} else {for (int k = 0; k < 2; ++k) {int rr = row + dir[k][0];int cc = col + dir[k][1];if (rr < 1 || cc < 1 || rr > m || cc > n)continue;if (sum - a[row][col] == dp[rr][cc]) {dfs(sum - a[row][col], rr, cc);}}}}public static void main(String[] args) {Scanner in = new Scanner(new BufferedInputStream(System.in));m = in.nextInt();n = in.nextInt();dp = new int[m + 1][n + 1];a = new int[m + 1][n + 1];// afor (int i = 1; i <= m; ++i) {for (int j = 1; j <= n; ++j)a[i][j] = in.nextInt();}// dpfor (int i = 1; i <= m; ++i) {for (int j = 1; j <= n; ++j) {// 因為有正負if (j == 1)dp[i][j] = dp[i - 1][j] + a[i][j];else if (i == 1)dp[i][j] = dp[i][j - 1] + a[i][j];elsedp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + a[i][j];}}// Util.print(dp);System.out.print(dp[m][n] + " ");dfs(dp[m][n], m, n);System.out.println(ans);}}

很遺憾 因為
Author
高見元
Organization
湖北經(jīng)濟學(xué)院
Code Size Limit
16 KB
Time Limit
1000 ms
Memory Limit
1 MB

總結(jié)

以上是生活随笔為你收集整理的PTA 寻宝路线 (40 point(s))的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。