GESP 题解库 / 7 级题解 / [GESP202409 七级] 矩阵移动 · 第 14 / 24 题
GESP202409 七级 · P11248 · 中等

矩阵移动

网格只能向右或向下走,还能把至多 x 个 ? 改成 1 —— 三维 DP + 滚动数组。

🧮
n, m ≤ 500
矩阵规模
✏️
x ≤ 300
最多改写个数
⚡
O(n·m·x)
时间复杂度
🎯
三维 DP + 滚动数组
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

小杨有一个 n × m 的矩阵,仅包含 0、1、? 三种字符。小杨从左上角 (1, 1) 出发,只能向下或向右移动,最终到达右下角 (n, m) 时停止。移动过程中每经过一个字符 1 就加 1 分(包括起点和终点),经过其它字符分数不变,初始 0 分。

小杨还可以把矩阵中不超过 x 个字符 ? 变为字符 1。修改之后,他会以最优策略从左上角走到右下角。求他最多能获得多少分。

第一行 t 组数据;每组第一行 n, m, x,随后 n 行每行一个长度为 m 的 01? 串。

💡
人话翻译:先"改矩阵"再"走路",目标是让最优路径上的 1 尽可能多。
关键在于:改写和走路是耦合的——改在哪几个格子,取决于最终会选择哪条路径。所以不能先贪心改写再走路,必须把"已经用掉几次改写"当作 DP 的一个维度,让 DP 自己决定"这条路径上把哪几个 ? 变成 1"。
于是状态就是:走到 (i, j)、已改写 k 个 ? 时的最大得分。

🔍 关键词提取

网格路径 DP状态多一维"改写次数"滚动数组"?" 的两种选择

已知条件

项目说明
输入t 组;每组 n, m, x 与 n 行长度为 m 的 01? 串
输出每组一个整数:最优策略下的最大得分
数据范围1 ≤ t ≤ 10,1 ≤ n, m ≤ 500,1 ≤ x ≤ 300
总量约束Σ(n × m) ≤ 2.5 × 10⁵(保证所有组加起来不超时)
计分范围起点和终点也计分(经过就算)

需要解决的问题

02
思维导图
整理解题思路的全貌
🧭 网格 DP 再加一维:已改写次数 k
🎯 状态定义
dp[i][j][k] = 到 (i, j) 用了 k 次改写的最大得分
k 的范围 0 … x
起点 dp[1][1][*] 按 (1,1) 的字符处理
答案 = max over k ≤ x
🔁 转移
从上方 (i−1, j) 或左方 (i, j−1) 取 max
字符 1 → 得分 +1,k 不变
字符 0 → 得分不变
字符 ? → 不改(+0)或改成 1(+1 且 k+1)
💾 空间优化
i 这一层只依赖 i−1 层
只需保留"上一行 + 当前行"
dp 大小 m × (x + 1) ≈ 500 × 301
约 1.2 MB,安全
⚠️ 易错点
答案取 max 而不是 dp[x]
起点终点漏加 1 分
k 越界(k + 1 > x 时不能转移)
多组数据要重新初始化 dp
03
样例手算推导
两组样例的路子枚举推演

🧮 样例 1 第 1 组:矩阵 000 / 111 / 01?,x = 1,答案 4

3 × 3 的网格从 (1,1) 到 (3,3),每条路径恰好经过 5 个格子,一共只有 C(4, 2) = 6 条路径。全部枚举一遍就能看清最优点。

路径(5 个格子)其中 '1' 的个数其中 '?' 的个数得分 = 1 的个数 + min(x, ? 的个数)
(1,1)(1,2)(1,3)(2,3)(3,3)111 + min(1,1) = 2
(1,1)(1,2)(2,2)(2,3)(3,3)212 + 1 = 3
(1,1)(1,2)(2,2)(3,2)(3,3)212 + 1 = 3
(1,1)(2,1)(2,2)(2,3)(3,3)313 + 1 = 4
(1,1)(2,1)(2,2)(3,2)(3,3)313 + 1 = 4
(1,1)(2,1)(3,1)(3,2)(3,3)212 + 1 = 3
1
结论

第 4、5 条路径都经过第二行的 3 个 1,加起点 0 分,共 3 分

再把终点 (3,3) 的 ? 改成 1,得到 3 + 1 = 4 分

x = 1 只够改一个 ?,正好够用

✅ 答案 4

🔑
注意第 4 条路径的走法:(1,1) → (2,1) → (2,2) → (2,3) → (3,3),先向下钻进第二行,把 111 一行吃干净,再顺着最后一列向下到终点。这条路径上恰好只有 1 个 ?,所以 x = 1 刚好能把它变成 1。如果最优路径上有 3 个 ? 而 x = 1,就只能改其中 1 个。

🧮 样例 1 第 2 组:矩阵 000 / ?0? / 01?,x = 1,答案 2

这一组 ? 更多(一共有 3 个),但 x 只有 1,所以每条路径的得分都会被 min(x, ? 的个数) 卡住。

路径(5 个格子)其中 '1' 的个数其中 '?' 的个数得分 = 1 的个数 + min(x, ? 的个数)
(1,1)(1,2)(1,3)(2,3)(3,3)020 + min(1,2) = 1
(1,1)(1,2)(2,2)(2,3)(3,3)021
(1,1)(1,2)(2,2)(3,2)(3,3)111 + 1 = 2
(1,1)(2,1)(2,2)(2,3)(3,3)030 + 1 = 1
(1,1)(2,1)(2,2)(3,2)(3,3)121 + 1 = 2
(1,1)(2,1)(3,1)(3,2)(3,3)121 + 1 = 2

📊 三种"改法"对照

策略结果说明
不改 ?(k 恒为 0)最多 1 分只有路径上真实存在的 1 才算分
见 ? 就改(贪心满额)会被 x 卡住路径上 3 个 ? 也只能改 1 个
把改写额度用在刀刃上(DP)2 分选一条 1 与 ? 搭配最好的路径
⚠️
这一组最有价值的地方:第 2 条路径经过 2 个 ? 却只有 0 个 1,两个 ? 只能改 1 个 → 1 分;而第 3 条路径有 1 个 1 和 1 个 ?,正好凑成 2 分。
这说明"路径上的 ? 越多越好"是错的——因为改写额度有限,? 太多反而浪费。DP 会自动在"1 多的路径"和"? 数量刚好用满的路径"之间做权衡。
04
解法对比
三维 DP(滚动数组)vs 先贪心改写再走

⚔️ 解法对比

🟢 三维 DP + 滚动数组(推荐) 推荐

dp[j][k] 表示"走到当前行第 j 列、已改写 k 个 ?"的最大得分

  • 时间 O(n·m·x)
  • 空间 O(m·x) 只留一行
  • 转移 4 行写完
  • 天然处理"不改 / 改"两种选择
💡
滚动数组为什么能省空间:第 i 行的状态只由第 i − 1 行(上方)和本行左边一格推出来,所以只保留一行 dp 即可,每格原地更新(枚举 k 时从大到小)。

🟠 先贪心改写、再走一次最大路径

先决定改哪些 ?,再求"最大 1 路径"

  • 看起来简单
  • 但改哪些 ? 取决于走哪条路
  • 两步互相耦合,无法解耦
  • 贪心会被反例击穿
⚠️
反例:样例 1 第 2 组中,若把 ? 改在 (2,1) 附近,看似"最贵的格子先改",但最优路径其实走的是 (1,2)(2,2)(3,2) 这一列,改偏了就一分不赚。所以必须让 DP 把"改写"和"走法"一起决策。

📈 性能对比

方案复杂度代码量
三维 DP + 滚动数组O(n·m·x) ≈ 7.5 × 10⁷约 40 行
三维 DP(不滚动)空间 O(n·m·x) ≈ 150 MB⚠️ 会超内存
暴力枚举路径指数级❌ 不可行
05
算法流程图
逐格转移:多一维 k 记录改写次数
开始:读入 n, m, x 与矩阵 gdp[1..m][0..x] 全部置为 −∞(表示不可达)当前处理的是起点 (1,1) 吗?是 ✓分数从 0 起步,只允许 k = 0否 ✗分数 base = max(上方 dp[j][k], 左方 dp[j−1][k]),不可达则跳过格子字符 ch 是什么?ch = 1dp[j][k] = base + 1(k 不变)ch = 0dp[j][k] = base(分数不变)ch = ?不改:dp[j][k] = base;改:dp[j][k+1] = max(…, base + 1)所有 (i, j) 与 k ≤ x 都处理完了吗?答案 = max(dp[m][k]),k = 0 … x继续下一个格子
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

🧭 矩阵移动最大得分

第一行输入 n m x,随后 n 行每行 m 个字符(0/1/?)。程序用三维 DP(滚动数组)求最大得分;当路径条数不多时,还会把所有路径列出来帮你核对。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码(三维 DP + 原地滚动数组)

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

const int NEG = -1000000000;   // −∞:表示"不可达"

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        int n, m, x;
        scanf("%d %d %d", &n, &m, &x);
        vector<string> g(n);
        for (int i = 0; i < n; i++) {
            char buf[1005];
            scanf("%s", buf);
            g[i] = buf;
        }

        // dp[j][k]:走到"当前行"第 j 列、已把 k 个 '?' 改成 '1' 时的最大得分
        // 原地更新:dp[j][k] 更新前代表"上方格子"的值,dp[j-1][k] 已是"左方格子"的新值
        vector<vector<int>> dp(m, vector<int>(x + 1, NEG));

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                char ch = g[i][j];
                for (int k = x; k >= 0; k--) {          // 从大到小,保证 '?' 转移不重复
                    int base;
                    if (i == 0 && j == 0) {
                        base = (k == 0 ? 0 : NEG);      // 起点:0 分起步
                    } else {
                        base = dp[j][k];                // 来自上方
                        if (j > 0) base = max(base, dp[j - 1][k]);   // 来自左方
                    }
                    if (base == NEG) continue;          // 不可达,跳过

                    if (ch == '1') {
                        dp[j][k] = base + 1;            // 白捡 1 分
                    } else if (ch == '0') {
                        dp[j][k] = base;                // 分数不变
                    } else {                            // ch == '?'
                        dp[j][k] = base;                // 选择一:不改
                        if (k + 1 <= x)                 // 选择二:改成 '1'
                            dp[j][k + 1] = max(dp[j][k + 1], base + 1);
                    }
                }
            }
        }

        int ans = NEG;
        for (int k = 0; k <= x; k++) ans = max(ans, dp[m - 1][k]);
        printf("%d\n", ans);
    }
    return 0;
}
🔑
为什么 k 要从大到小枚举?因为 ? 的"改成 1"是一条 k → k + 1 的转移,会写到更大的下标。若从小到大枚举,刚写进 dp[j][k+1] 的值会在本轮又被当成"base" 继续往 k+2 传,相当于一个 ? 被改了两次。
从大到小枚举时,写到的 k + 1 已经处理过了,本轮不会再被读,逻辑就对了。

📖 关键几行怎么看

代码作用为什么这样写
vector<vector<int>> dp(m, vector<int>(x+1, NEG));滚动数组只保留一行,空间从 O(n·m·x) 降到 O(m·x)
base = max(dp[j][k], dp[j−1][k])两个来源dp[j][k] 更新前是上方,dp[j−1][k] 是左方
if (i == 0 && j == 0) base = (k == 0 ? 0 : NEG);起点初始化起点只允许 k = 0,且分数从 0 开始
if (ch == '1') dp[j][k] = base + 1;计分起点终点也计分,所以起点若是 1 也会加 1
for (int k = x; k >= 0; k--)枚举顺序? 转移写 k+1,必须从大到小
for (int k = 0; k <= x; k++) ans = max(ans, dp[m−1][k]);取答案题目是"不超过 x 个",所以要对所有 k 取 max
⚠️
四个坑:① 答案只看 dp[m−1][x]:题目说"不超过 x 个",必须对所有 k ≤ x 取最大值;② k 从小到大枚举导致同一个 ? 被重复改写;③ 起点 (1,1) 忘了按字符处理(起点是 1 时应该得 1 分);④ 不开 long long 没关系(得分 ≤ n + m − 1 ≤ 999),但 NEG 一定要足够小,且判断不可达不能用 base == −1。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
2
3 3 1
000
111
01?
3 3 1
000
?0?
01?
4
2
题面样例(两组)
1
1 1 1
?
1单格是 ?,改成 1 得 1 分
1
1 1 1
0
0单格是 0,拿不到分
1
2 2 1
??
??
1全问号 2×2:路径只有 3 格,x = 1 只能改 1 个
1
1 3 2
???
2单行 3 格,x = 2 改 2 个
1
2 2 2
1?
?1
3起点终点都是 1,沿途再改 1 个 ?
1
1 2 300
??
2x 远大于 ? 的个数,注意"至多"语义
1
3 1 1
1
0
1
2只有一列,路径唯一
1
3 4 2
1111
1??1
1111
63×4,路径长 6,可走全 1 的那条
✅
自查清单:① dp 多了一维 k 吗?② k 是从大到小枚举吗?③ 答案对 k ≤ x 取 max 吗?④ 起点按字符处理了吗?

🚨 易错点清单

⚠️
答案只取 dp[m][x]:题目是"不超过 x 个 ?",答案必须对 k = 0 … x 取最大值。
⚠️
k 枚举方向错:? 的转移会写到 k + 1,必须从大到小枚举 k,否则同一个 ? 会被改多次。
⚠️
起点终点漏算:题目明确"包括起点和终点",起点是 1 时也要加 1 分。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(n·m·x)
空间复杂度
O(m·x)
运算量
约 7.5 × 10⁷
单组内存
约 1.2 MB

时间怎么算的?

空间都用在哪?

滚动数组只保留一行:m × (x + 1) 个 int,即 500 × 301 × 4 B ≈ 602 KB,两倍余量也才 1.2 MB。
若不用滚动,n × m × (x + 1) 个 int 可达 500 × 500 × 301 × 4 B ≈ 301 MB,直接爆内存。

✅ 7.5 × 10⁷ 次 O(1) 转移,C++ 下约 0.2 ~ 0.4 s,滚动数组是本题能否通过的关键:它把空间从 300 MB 压到不足 1 MB。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// 核心转移:dp[j][k] = 走到当前行第 j 列、已改写 k 个 '?' 的最大得分
for (int i = 0; i < n; i++)
  for (int j = 0; j < m; j++)
    for (int k = x; k >= 0; k--) {          // 从大到小!
      int base;
      if (i == 0 && j == 0) base = (k == 0 ? 0 : -INF);
      else {
        base = dp[j][k];                    // 上方(尚未被本行覆盖)
        if (j > 0) base = max(base, dp[j-1][k]);   // 左方(本行已更新)
      }
      if (base == -INF) continue;
      char ch = g[i][j];
      if (ch == '1')      dp[j][k] = base + 1;                       // 白捡 1 分
      else if (ch == '0') dp[j][k] = base;                           // 不加分
      else {                                                          // '?'
        dp[j][k] = base;                                             // 不改
        if (k + 1 <= x) dp[j][k+1] = max(dp[j][k+1], base + 1);       // 改成 1
      }
    }

// 答案:题目是"不超过 x 个",所以对所有 k ≤ x 取最大值
int ans = -INF;
for (int k = 0; k <= x; k++) ans = max(ans, dp[m-1][k]);

🌟 举一反三

把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。

能力点本题怎么用还能迁移到
网格路径 DP只能向右/向下 → 逐格转移棋盘路径计数、网格最短路、数字三角形
状态多一维把"已改写次数"记成 k背包容量、限次操作、配对/翻转次数
滚动数组第 i 行只依赖第 i − 1 行与左边一格所有大规模 DP 的空间压缩
"不超过"型约束答案对 k ≤ x 取 max"至多 k 次操作"、"预算不超过 B" 的统一处理
🌟
思考题:如果题目改成"必须恰好把 x 个 ? 改成 1"(保证矩阵里 ? 的总数不少于 x),答案会变吗?
(提示:不会变。因为改写是作用在整个矩阵上的,不要求全在路径上:只要矩阵里还有够多的 ?,把"路径上需要的改写"用完之后,剩下的额度随便找一些路径外的 ? 改掉,既凑够"恰好 x 个",又完全不改变路径得分。所以"至多 x 个"与"恰好 x 个"在这道题里是等价的——读题时看清"额度用在哪、能不能浪费"往往比多做几步 DP 更重要。)