Loading... # [NOIP2000 提高组] 方格取数 ## 题目描述 设有 $N \times N$ 的方格图 $(N \le 9)$,我们将其中的某些方格中填入正整数,而其他的方格中则放入数字 $0$。如下图所示(见样例): ```plain A 0 0 0 0 0 0 0 0 0 0 13 0 0 6 0 0 0 0 0 0 7 0 0 0 0 0 0 14 0 0 0 0 0 21 0 0 0 4 0 0 0 0 15 0 0 0 0 0 0 14 0 0 0 0 0 0 0 0 0 0 0 0 0 0 B ``` 某人从图的左上角的 $A$ 点出发,可以向下行走,也可以向右走,直到到达右下角的 $B$ 点。在走过的路上,他可以取走方格中的数(取走后的方格中将变为数字 $0$)。 此人从 $A$ 点到 $B$ 点共走两次,试找出 $2$ 条这样的路径,使得取得的数之和为最大。 ## 输入格式 输入的第一行为一个整数 $N$(表示 $N \times N$ 的方格图),接下来的每行有三个整数,前两个表示位置,第三个数为该位置上所放的数。一行单独的 $0$ 表示输入结束。 ## 输出格式 只需输出一个整数,表示 $2$ 条路径上取得的最大的和。 ## 样例 #1 ### 样例输入 #1 ``` 8 2 3 13 2 6 6 3 5 7 4 4 14 5 2 21 5 6 4 6 3 15 7 2 14 0 0 0 ``` ### 样例输出 #1 ``` 67 ``` ## 提示 NOIP 2000 提高组第四题 # 解析 这题,是四维动规的模板题,和P1006传纸条基本相似。 我们考虑两个人同时走,就相当于数字三角形。状态转移方程为: $$ f[i][j][k][l]=max(f[i-1][j][k-1][l], f[i-1][j][k][l-1], f[i][j-1][k-1][l],f[i][j-1][k][l-1])+a[i][j]+a[k][l] $$ 不过要判断`i==k&&j==l`的情况。 代码如下: ```java import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int f[][][][] = new int[12][12][12][12]; int a[][] = new int[12][12]; int n, x, y, z; // 输入n n = sc.nextInt(); // 输入处理 while(true) { x = sc.nextInt(); y = sc.nextInt(); z = sc.nextInt(); // 退出条件 if (x == 0 && y == 0 && z == 0) { break; } a[x][y] = z; } for (int i = 1; i <= n; i ++) { for (int j = 1; j <= n; j ++) { for (int k = 1; k <= n; k ++) { for (int l = 1; l <= n; l ++) { int max = f[i - 1][j][k - 1][l]; if (max < f[i - 1][j][k][l - 1]) { max = f[i - 1][j][k][l - 1]; } if (max < f[i][j - 1][k - 1][l]) { max = f[i][j - 1][k - 1][l]; } if (max < f[i][j - 1][k][l - 1]) { max = f[i][j - 1][k][l - 1]; } f[i][j][k][l] = max + a[i][j] + a[k][l]; if (i == k && j == l) f[i][j][k][l] -= a[i][j]; } } } } System.out.println(f[n][n][n][n]); } } ``` 最后修改:2022 年 07 月 03 日 © 允许规范转载 打赏 赞赏作者 支付宝微信 赞 如果觉得我的文章对你有用,请随意赞赏