【NOIP提高组】方格取数
【NOIP提高组】方格取数
| 💖The Begin💖点点关注，收藏不迷路💖 |
设有N*N的方格图，我们将其中的某些方格填入正整数， 而其他的方格中放入0。 某人从图得左上角出发，可以向下走，也可以向右走，直到到达右下角。 在走过的路上，他取走了方格中的数。（取走后方格中数字变为0） 此人从左上角到右下角共走3次，试找出3条路径，使得取得的数总和最大。
输入：
第一行:N (4< =N< =20) 接下来一个N*N的矩阵，矩阵中每个元素不超过80，不小于0
输出：
一行，表示最大的总和。
样例输入：
3
1 1 10
1 3 5
2 2 6
2 3 4
3 1 8
3 2 2
0 0 0
样例输出：
30
#include <stdio.h>
#include <stdlib.h>#define MAX_N 10 // 定义最大值常量int n; // 定义整数变量n
int a[MAX_N + 1][MAX_N + 1]; // 定义二维数组a
int f[(MAX_N * 2) + 1][MAX_N + 1][MAX_N + 1]; // 定义三维数组fint main() {int i, j, k, x, y; // 定义整数变量i, j, k, x, yscanf("%d", &n); // 从标准输入读取n的值// 读取i, j, k的值，直到i为0，将k赋值给a[i][j]while (scanf("%d%d%d", &i, &j, &k), i != 0) {a[i][j] = k;}f[1][1][1] = a[1][1]; // 将a[1][1]的值赋给f[1][1][1]// 循环计算最大路径和for (k = 2; k < (n * 2); k++) {for (i = 1; i <= k && i <= n; i++) {for (j = 1; j <= k && j <= n; j++) {// 计算x的值if (i == j) {x = a[i][k + 1 - i];} else {x = a[i][k + 1 - i] + a[j][k + 1 - j];}y = f[k - 1][i][j]; // 初始化y为f[k-1][i][j]// 更新y为四个方向的最大值if (f[k - 1][i - 1][j - 1] > y) {y = f[k - 1][i - 1][j - 1];}if (f[k - 1][i][j - 1] > y) {y = f[k - 1][i][j - 1];}if (f[k - 1][i - 1][j] > y) {y = f[k - 1][i - 1][j];}f[k][i][j] = x + y; // 计算当前位置的最大路径和}}}printf("%d\n", f[n * 2 - 1][n][n]); // 输出最终结果return 0;
}
这段代码实现的是一个动态规划算法，用于求解一个二维矩阵中从起点到终点的最大路径和。
1、首先，我们定义了一个二维数组 a 用于存储输入的矩阵。然后，我们定义了一个三维数组 f 作为状态数组，用于存储每个位置的最大路径和。
2、接下来，我们遍历 k，表示路径长度。对于每个 k 值，我们使用三重循环遍历矩阵的每个位置 (i, j)，其中 i 和 j 分别表示当前位置的行和列。
在每个位置 (i, j)，我们根据不同的情况计算出路径长度为 k 时的最大路径和：
- 如果
i等于j，说明当前位置在矩阵的主对角线上，此时路径长度为k的最大路径和等于当前位置的值a[i][k+1-i]。 - 如果
i不等于j，说明当前位置不在主对角线上，此时路径长度为k的最大路径和等于当前位置的值a[i][k+1-i]加上位置(i, j)左上方和右上方两个位置的最大路径和中的较大值。
3、最后，我们输出 f[n*2-1][n][n]，即路径长度为 n*2-1（矩阵中元素数的两倍减一）时，终点位置 (n, n) 的最大路径和。
该算法通过动态规划的思想，利用已计算出的较小路径长度的最大路径和，逐步推导得到较大路径长度的最大路径和，最终得到了问题的解。
| 💖The End💖点点关注，收藏不迷路💖 |