复赛4:方格取数(number)

洛谷：P7074
OJ: P4969

代码分析：

  1. 输入与矩阵初始化：
    • 首先，读取矩阵的大小 n 和 m。
    • 接下来，读取每个方格的整数值存入二维数组 a 中。
  2. 动态规划数组初始化：
    • 动态规划数组 f 和 g 用于存储小熊走到每个位置时所能获得的最大整数和。
    • 为了方便处理边界情况，将所有数组的初始值设为极小值 -1e18，代表小熊不可能到达该位置。
  3. 自顶向下和自底向上的动态规划：
    • f[i][j] 表示小熊从左上角到达 (i,j) 位置时，通过自顶向下的方式所能获得的最大整数和。
    • g[i][j] 表示小熊从左上角到达 (i,j) 位置时，通过自底向上的方式所能获得的最大整数和。
  4. 递推更新：
    • 首先从左到右遍历每一列。
    • 在每一列中，先从上到下更新 f[i][j]，然后从下到上更新 g[i][j]。
    • 每次更新后，将 f[i][j] 和 g[i][j] 中的最大值存回 f[i][j]，确保每个位置的最大值。
  5. 结果输出：
    • 最终结果是 f[n][m]，即小熊到达右下角 (n, m) 的最大整数和。

关键逻辑：

  • 通过两次遍历每一列，一次自顶向下，一次自底向上，确保计算出小熊从左上角走到右下角时，所有可能路径的最大整数和。
  • 该解法利用动态规划避免重复计算，时间复杂度为 $O(n*m)$，适合较大的输入规模。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <iostream>
using namespace std;

int n, m;  // n 行 m 列的矩阵大小
int a[1010][1010];  // 存储每个方格中的整数值
long long f[1010][1010];  // 自顶向下的最大值动态规划数组
long long g[1010][1010];  // 自底向上的最大值动态规划数组

int main() {
    // 输入矩阵的行数 n 和列数 m
    cin >> n >> m;
    
    // 读取每个方格的整数值到矩阵 a 中
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
        }
    }
    
    // 初始化动态规划数组 f 和 g
    // 初始时所有位置设为极小值，因为表示不可能到达的位置（相当于 -∞）
    for (int i = 0; i <= n + 1; i++) {
        for (int j = 0; j <= m + 1; j++) {
            f[i][j] = g[i][j] = -1e18;  // -1e18 表示负无穷大
        }
    }
    
    // 起点位置为矩阵左上角（1,1），起始值为 a[1][1]
    f[1][1] = a[1][1];
    
    // 从左到右遍历每一列
    for (int j = 1; j <= m; j++) {
        // 自顶向下遍历每一行，计算 f 数组（自顶向下走的最大值）
        for (int i = 1; i <= n; i++) {
            // 从左边到达当前位置的最大值
            f[i][j] = max(f[i][j], f[i][j - 1] + a[i][j]);
            // 从上边到达当前位置的最大值
            if (i > 1) {
                f[i][j] = max(f[i][j], f[i - 1][j] + a[i][j]);
            }
        }
        
        // 自底向上遍历每一行，计算 g 数组（自底向上走的最大值）
        for (int i = n; i >= 1; i--) {
            // 从左边到达当前位置的最大值
            g[i][j] = max(g[i][j], f[i][j - 1] + a[i][j]);
            // 从下边到达当前位置的最大值
            if (i < n) {
                g[i][j] = max(g[i][j], g[i + 1][j] + a[i][j]);
            }
        }
        
        // 更新 f 数组，确保当前位置的最大值
        // 既要考虑从上到下的值 f[i][j]，也要考虑从下到上的值 g[i][j]
        for (int i = 1; i <= n; i++) {
            f[i][j] = max(f[i][j], g[i][j]);
        }
    }
    
    // 最终结果为矩阵右下角的值，即到达 (n, m) 位置的最大值
    cout << f[n][m] << endl;
    
    return 0;
}
Previous Topic
Back to Lesson
Next Quiz