CSP 真题解析：[CSP-J 2020-T4] 方格取数

[CSP-J 2020-T4] 方格取数摘要本文解析 CSP‑J 2020 第四题「方格取数」的解题思路采用三维动态规划分别记录向上、向下、向右三个方向处理小熊从左上走到右下取数之和的最大值包含状态定义、边界初始化与转移方程并附 C 实现代码。题目描述设有n × m n \times mn×m的方格图每个方格中都有一个整数。现有一只小熊想从图的左上角走到右下角每一步只能向上、向下或向右走一格并且不能重复经过已经走过的方格也不能走出边界。小熊会取走所有经过的方格中的整数求它能取到的整数之和的最大值。输入格式第一行有两个整数n , m n, mn,m。接下来n nn行每行m mm个整数依次代表每个方格中的整数。输出格式一个整数表示小熊能取到的整数之和的最大值。输入输出样例 #1输入 #13 4 1 -1 3 2 2 -1 4 -1 -2 2 -3 -1输出 #19输入输出样例 #2输入 #22 5 -1 -1 -3 -2 -7 -2 -1 -4 -1 -2输出 #2-10说明/提示样例 1 解释样例 2 解释数据规模与约定对于20 % 20\%20%的数据n , m ≤ 5 n, m \le 5n,m≤5。对于40 % 40\%40%的数据n , m ≤ 50 n, m \le 50n,m≤50。对于70 % 70\%70%的数据n , m ≤ 300 n, m \le 300n,m≤300。对于100 % 100\%100%的数据1 ≤ n , m ≤ 10 3 1 \le n,m \le 10^31≤n,m≤103。方格中整数的绝对值不超过10 4 10^4104。2024/2/4 添加一组 hack 数据。思路要点​ 本题可以向上向下和向右走并且不能重复经过已经走过的方格因此向下和向上是不可能先后出现的用一个二维 dp 同时推三个方向就会有问题。​ 对于每个点接下来朝三个可选方向的走法是依其上一步走的方向而定的比如上一步是向下走的该处点就不能向上走了不然又会回到上一步的点。我们可以用三个二维数组分别记录 (i, j) 选择不同方向的结果。​ 由于横向只能往右走因此可以从左往右推每一列对每列再分别讨论该点朝上和朝下的情况。状态定义​d[i][j]从上往向下走到达 (i, j) 的取数之和最大值​r[i][j]从左往右走到达 (i, j) 的取数之和最大值​u[i][j]从下往上走到达 (i, j) 的取数之和最大值边界初始化对起点来说不存在上一步该点结果三个方向都为a[1][1]d[1][1] u[1][1] r[1][1] a[1][1];对第一列元素来说只能从上往下走得到可以用前缀和求出d[i][1] d[i - 1][1] a[i][1]。状态转移分三种情况讨论→↓↑。推 → 上一步可以是 ↑ 或 ↓ 或 →。r[i][j]a[i][j]max(max(u[i][j-1], d[i][j-1]), r[i][j-1])推 ↓ 上一步只能是 ↓ 或 →d[i][j] a[i][j] max(r[i - 1][j], d[i - 1][j])推 ↑ 上一步只能是 ↑ 或 →u[i][j] a[i][j] max(u[i 1][j], r[i 1][j])注意本题数据比较大数组要用 long long 存因为题目中a[i][j]可以是负数三个方向数组都要初始化为很小的数才能保证比较的正确性。参考代码#includebits/stdc.h#definemaxn1005usingnamespacestd;typedeflonglongll;intn,m,a[maxn][maxn];ll d[maxn][maxn],u[maxn][maxn],r[maxn][maxn];intmain(){scanf(%d %d,n,m);for(inti1;in;i){for(intj1;jm;j){scanf(%d,a[i][j]);d[i][j]u[i][j]r[i][j]LONG_LONG_MIN;}if(i1)// 对起点来说不存在上一步该点结果三个方向都为 a[1][1]d[1][1]u[1][1]r[1][1]a[1][1];else// i: 2 ~ n, ↓ 推 d[i][1] 初始化第一列值d[i][1]d[i-1][1]a[i][1];}for(intj2;jm;j){// 从第一列开始推 2 ~ m 列for(inti1;in;i)// 推 → 上一步可以是 ↑ 或 ↓ 或 →r[i][j]a[i][j]max(max(u[i][j-1],d[i][j-1]),r[i][j-1]);for(inti2;in;i)// 推 ↓ 上一步只能是 ↓ 或 →d[i][j]a[i][j]max(r[i-1][j],d[i-1][j]);for(intin-1;i1;i--)// 推 ↑ 上一步只能是 ↑ 或 →u[i][j]a[i][j]max(u[i1][j],r[i1][j]);}printf(%lld,max(max(u[n][m],d[n][m]),r[n][m]));return0;}