网格只能向右或向下走,还能把至多 x 个 ? 改成 1 —— 三维 DP + 滚动数组。
小杨有一个 n × m 的矩阵,仅包含 0、1、? 三种字符。小杨从左上角 (1, 1) 出发,只能向下或向右移动,最终到达右下角 (n, m) 时停止。移动过程中每经过一个字符 1 就加 1 分(包括起点和终点),经过其它字符分数不变,初始 0 分。
小杨还可以把矩阵中不超过 x 个字符 ? 变为字符 1。修改之后,他会以最优策略从左上角走到右下角。求他最多能获得多少分。
第一行 t 组数据;每组第一行 n, m, x,随后 n 行每行一个长度为 m 的 01? 串。
1 尽可能多。? 变成 1"。? 时的最大得分。网格路径 DP状态多一维"改写次数"滚动数组"?" 的两种选择
| 项目 | 说明 |
|---|---|
| 输入 | t 组;每组 n, m, x 与 n 行长度为 m 的 01? 串 |
| 输出 | 每组一个整数:最优策略下的最大得分 |
| 数据范围 | 1 ≤ t ≤ 10,1 ≤ n, m ≤ 500,1 ≤ x ≤ 300 |
| 总量约束 | Σ(n × m) ≤ 2.5 × 10⁵(保证所有组加起来不超时) |
| 计分范围 | 起点和终点也计分(经过就算) |
? 值不值,取决于那条路径最终是否经过它。先改后走会改在"没走到的格子"上,白白浪费改写次数? 做"不改 / 改成 1"两种选择即可max( dp[n][m][k] ),k = 0 … x,而不是只看 dp[n][m][x]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) | 1 | 1 | 1 + min(1,1) = 2 |
| (1,1)(1,2)(2,2)(2,3)(3,3) | 2 | 1 | 2 + 1 = 3 |
| (1,1)(1,2)(2,2)(3,2)(3,3) | 2 | 1 | 2 + 1 = 3 |
| (1,1)(2,1)(2,2)(2,3)(3,3) | 3 | 1 | 3 + 1 = 4 |
| (1,1)(2,1)(2,2)(3,2)(3,3) | 3 | 1 | 3 + 1 = 4 |
| (1,1)(2,1)(3,1)(3,2)(3,3) | 2 | 1 | 2 + 1 = 3 |
第 4、5 条路径都经过第二行的 3 个 1,加起点 0 分,共 3 分
再把终点 (3,3) 的 ? 改成 1,得到 3 + 1 = 4 分
x = 1 只够改一个 ?,正好够用
✅ 答案 4
(1,1) → (2,1) → (2,2) → (2,3) → (3,3),先向下钻进第二行,把 111 一行吃干净,再顺着最后一列向下到终点。这条路径上恰好只有 1 个 ?,所以 x = 1 刚好能把它变成 1。如果最优路径上有 3 个 ? 而 x = 1,就只能改其中 1 个。这一组 ? 更多(一共有 3 个),但 x 只有 1,所以每条路径的得分都会被 min(x, ? 的个数) 卡住。
| 路径(5 个格子) | 其中 '1' 的个数 | 其中 '?' 的个数 | 得分 = 1 的个数 + min(x, ? 的个数) |
|---|---|---|---|
| (1,1)(1,2)(1,3)(2,3)(3,3) | 0 | 2 | 0 + min(1,2) = 1 |
| (1,1)(1,2)(2,2)(2,3)(3,3) | 0 | 2 | 1 |
| (1,1)(1,2)(2,2)(3,2)(3,3) | 1 | 1 | 1 + 1 = 2 |
| (1,1)(2,1)(2,2)(2,3)(3,3) | 0 | 3 | 0 + 1 = 1 |
| (1,1)(2,1)(2,2)(3,2)(3,3) | 1 | 2 | 1 + 1 = 2 |
| (1,1)(2,1)(3,1)(3,2)(3,3) | 1 | 2 | 1 + 1 = 2 |
| 策略 | 结果 | 说明 |
|---|---|---|
不改 ?(k 恒为 0) | 最多 1 分 | 只有路径上真实存在的 1 才算分 |
见 ? 就改(贪心满额) | 会被 x 卡住 | 路径上 3 个 ? 也只能改 1 个 |
| 把改写额度用在刀刃上(DP) | 2 分 | 选一条 1 与 ? 搭配最好的路径 |
? 却只有 0 个 1,两个 ? 只能改 1 个 → 1 分;而第 3 条路径有 1 个 1 和 1 个 ?,正好凑成 2 分。dp[j][k] 表示"走到当前行第 j 列、已改写 k 个 ?"的最大得分
先决定改哪些 ?,再求"最大 1 路径"
? 改在 (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 | ⚠️ 会超内存 |
| 暴力枚举路径 | 指数级 | ❌ 不可行 |
第一行输入 n m x,随后 n 行每行 m 个字符(0/1/?)。程序用三维 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; }
? 的"改成 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。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
2 | 4 2 | 题面样例(两组) |
1 | 1 | 单格是 ?,改成 1 得 1 分 |
1 | 0 | 单格是 0,拿不到分 |
1 | 1 | 全问号 2×2:路径只有 3 格,x = 1 只能改 1 个 |
1 | 2 | 单行 3 格,x = 2 改 2 个 |
1 | 3 | 起点终点都是 1,沿途再改 1 个 ? |
1 | 2 | x 远大于 ? 的个数,注意"至多"语义 |
1 | 2 | 只有一列,路径唯一 |
1 | 6 | 3×4,路径长 6,可走全 1 的那条 |
? 的转移会写到 k + 1,必须从大到小枚举 k,否则同一个 ? 会被改多次。1 时也要加 1 分。n × m × (x + 1)Σ(n × m) ≤ 2.5 × 10⁵,所有组的状态总和 ≤ 2.5 × 10⁵ × 301 ≈ 7.5 × 10⁷滚动数组只保留一行: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。
// 核心转移: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" 的统一处理 |
? 改成 1"(保证矩阵里 ? 的总数不少于 x),答案会变吗??,把"路径上需要的改写"用完之后,剩下的额度随便找一些路径外的 ? 改掉,既凑够"恰好 x 个",又完全不改变路径得分。所以"至多 x 个"与"恰好 x 个"在这道题里是等价的——读题时看清"额度用在哪、能不能浪费"往往比多做几步 DP 更重要。)