CSP-J 2020 真题精讲(下):方格取数

文章首发于公众号 CSP信奥资料交流共享，专注信息学奥赛资料与经验分享。

本期是「CSP-J/S 历年真题精讲」系列第 5 篇，精讲 CSP-J 2020 年 T4「方格取数」—— 一道经典的双路 DP 压轴题。

一、写在前面

CSP-J 2020 T4「方格取数」是一道经典的双路动态规划题。它考察的是：如何在同一个网格中同时规划两条路径，使得总收益最大。

实战策略：T4 是 2020 年 CSP-J T1~T4 中最难的一道。对于基础薄弱的同学，先写单条路径的最大和 DP，稳拿 30 分；有余力的再冲击满分。

二、题目背景（原题精炼）

给定一个 n × m 的网格（n, m <= 50），每个格子有一个正整数 a[i][j]。

要求从左上角 (1, 1) 出发，每次只能向右或向下走，到达右下角 (n, m)。需要走两次（即规划两条从 (1,1) 到 (n,m) 的路径），同一个格子第二次经过时不计入收益。求两条路径上收集的数字之和的最大值。

关键约束：每次只能向右或向下移动，每次移动 1 格。两条路径长度相同：都是 (n-1) + (m-1) 步。

三、考点分析

四、解题思路

思路 1：单条路径最大和（30 分）

经典的「数字三角形」型 DP：

dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + a[i][j]

只求一条从 (1,1) 到 (n,m) 的最大路径和。虽然不能解决原题，但这是保底的 30 分。

思路 2：贪心 —— 先走最优，再走次优（50 分）

先 DP 找到第一条最优路径，标记已走过的格子，再 DP 找第二条路径（避开已标记格子）。但贪心不保证全局最优 —— 第一条路径「太贪」可能让第二条路径无路可走。

思路 3：双路 DP（4D 状态）（70 分）

直接记录两条路径的位置：dp[i1][j1][i2][j2] = 路径 1 到 (i1,j1)、路径 2 到 (i2,j2) 时的最大和。状态转移：每条路径各选一种方向（右/下），共 4 种组合。

4D 状态数：n × m × n × m ≈ 50⁴ = 6.25 × 10⁶，勉强可过但内存较大。

思路 4：双路 DP + 同步优化（100 分）✅

关键洞察：两条路径同步走。因为只能向右/向下，第 k 步时每条路径的坐标满足：

i1 + j1 = i2 + j2 = k + 1

这样知道 i1、i2 后，j1 = k+1 - i1，j2 = k+1 - i2 自动确定！状态降为 dp[k][i1][i2]（3D），再用滚动数组压掉 k 维 → dp[2][n][n]。

4.1 状态转移

从 (i1,j1) 和 (i2,j2) 出发，每条路径各选一个方向：

增加值计算：

• 如果两条路径的新位置不同：add = a[ni1][nj1] + a[ni2][nj2]
• 如果两条路径走到同一格：add = a[ni1][nj1]（只计算一次）

五、完整代码

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 55;
const int INF = 0x3f3f3f3f;

int n, m;
int a[MAXN][MAXN];
int dp[2][MAXN][MAXN];  // 滚动数组：dp[cur][i1][i2]

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> a[i][j];
    
    // 初始化：所有状态不可达
    memset(dp, -0x3f, sizeof(dp));
    int cur = 0, nxt = 1;
    dp[cur][1][1] = a[1][1];  // 起点
    
    // 遍历步数 k（从第 2 步到第 n+m-1 步）
    for (int k = 2; k <= n + m - 1; k++) {
        memset(dp[nxt], -0x3f, sizeof(dp[nxt]));
        
        for (int i1 = 1; i1 <= n; i1++) {
            int j1 = k - i1 + 1;  // 修正：k = i1 + j1 - 1
            if (j1 < 1 || j1 > m) continue;
            
            for (int i2 = 1; i2 <= n; i2++) {
                int j2 = k - i2 + 1;
                if (j2 < 1 || j2 > m) continue;
                if (dp[cur][i1][i2] < -INF/2) continue;  // 不可达
                
                // 4 种方向组合：(di1, dj1) × (di2, dj2)
                int dirs[2][2] = {{0, 1}, {1, 0}};  // 右、下
                for (int d1 = 0; d1 < 2; d1++) {
                    int ni1 = i1 + dirs[d1][0];
                    int nj1 = j1 + dirs[d1][1];
                    if (ni1 > n || nj1 > m) continue;
                    
                    for (int d2 = 0; d2 < 2; d2++) {
                        int ni2 = i2 + dirs[d2][0];
                        int nj2 = j2 + dirs[d2][1];
                        if (ni2 > n || nj2 > m) continue;
                        
                        // 计算增加值：同一格只加一次
                        int add = a[ni1][nj1];
                        if (ni1 != ni2 || nj1 != nj2) {
                            add += a[ni2][nj2];
                        }
                        
                        dp[nxt][ni1][ni2] = max(
                            dp[nxt][ni1][ni2],
                            dp[cur][i1][i2] + add
                        );
                    }
                }
            }
        }
        swap(cur, nxt);  // 滚动
    }
    
    // 答案：两条路径都在右下角 (n, m)
    cout << dp[cur][n][n] << "\n";
    
    return 0;
}

关键点解释

1. k 的计算：k = i + j - 1，第 k 步时位置满足 i + j = k + 1。k 从 2（第一步走后）到 n+m-1（到达终点）
2. 同步走：两条路径每步都走一格，保证 k 值相同，这是降维的关键
3. 不可达判断：dp[cur][i1][i2] 初始为负无穷，转移时跳过不可达状态
4. 滚动数组：dp[2][n][n] 只需 O(n²) 内存

六、DP 执行过程一览

七、部分分策略

比赛建议：遇到 T4 压轴题不要慌！哪怕只写一个单路径 DP，也能稳稳拿到 30 分。对于大部分选手来说，这 30 分已经不影响获奖了。

八、易错点与练习

常见失误：

1. 忘记「两条路径同步走」的前提 —— 必须 i1+j1 = i2+j2
2. 两路径走到同一格时，只加一次值（不要加两次！）
3. dp 初始化为负无穷（不是 0），防止从未走过的状态转移
4. 滚动数组每轮要 memset 清零

练习题：

1. 洛谷 P1004 方格取数 —— 双路 DP 经典原型
2. 洛谷 P1006 传纸条 —— 双路 DP 变体
3. 洛谷 P7074 方格取数 —— 本题 CSP-J 2020 T4 原题
4. 洛谷 P1048 采药 —— 练习滚动数组优化

九、关联知识点

十、下一期预告

CSP-J 2021 真题精讲（上）：分糖果与插入排序

2021 年的 T1（分糖果）是一道看似简单但容易踩坑的模拟题，T2（插入排序）则需要理解排序的稳定性和优化技巧。下期带你一次通关！

关注公众号 CSP信奥资料交流共享，每日推送 CSP-J/S 真题精讲。双路 DP 是 CSP 复赛中难度天花板之一，攻克了它，其他 DP 题都不在话下！