首发题解，庆祝一下

大家好，我是энтджей，今天是我2026年第十九次正式发题解！

2026年发布的题解！

能不能点个赞

---

首先简化题意：

• 你在$（1,1）$你要到$（n,m）$去，在$（i,j）$上，当 $a_{i,j} = 0$ 时不得分； $a_{i,j} = 1$ 时得一分； $a_{i,j} = ?$ 你可以选择消耗一次机会（最多 $x$ 次）将 $?$ 变成 $1$，从而得一分，否则不得分。问到 $（n,m）$ 时的最大得分

然后就是写代码:

• 处理输入（read）：

  • 正常输入

• 核心部分（process）：

  • 这是一道比较标准的$dp$，定义$dp$数组：$dp[i][j][k]表示到（i,j）换了 k 次 ? 的最大得分$
  • $dp[i][j][k]$ 明显只能从 $dp[i - 1][j][k]、dp[i][j - 1][k]、dp[i - 1][j][k - 1]、dp[i][j - 1][k - 1]$来，特别的，当 $1 <= k$ ，后面两个才成立
  • 三重暴力循环，枚举 $i,j,k$ 计算得出结果

最后输出（write）：

• 输出结果

完整代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 510;
const int M = 310;

int T;
int n,m,x;
char a[N][N];
int dp[N][N][M];
void init() {
    for(int k = 0; k <= x; k++){
        for(int i = 0; i <= n; i++) { 
            for(int j = 0; j <= m; j++) {
                dp[i][j][k] = 0;
            }
        }
    }
}
void read() {
    cin >> n >> m >> x;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            cin >> a[i][j];
        }
    }
}
void process() {
    init();
    for(int k = 0; k <= x; k++){
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                dp[i][j][k] = (k > 0 && a[i][j] == '?') ? max(max(dp[i - 1][j][k], dp[i][j - 1][k]), max(dp[i - 1][j][k - 1], dp[i][j - 1][k - 1]) + 1) : max(dp[i - 1][j][k], dp[i][j - 1][k]) + ((a[i][j] == '1') ? 1 : 0);
            }
        }
    }
}

void write() {
    int ans = 0;
    for(int k = 0; k <= x; k++) {
        ans = max(ans, dp[n][m][k]);
    }
    cout << ans << endl;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);

    cin >> T;
    while(T--){
        read();
        process();
        write();
    }
    return 0;
}

---

🎉完结撒花🎉