题目传送门

题目大意

给出一个 $n$ 行 $m$ 列的只包含 0、1、? 的矩阵，你可以选择至多 $x$ 个 ? 改成 1。

设得分为经过的 1 的数量，求从矩阵的 $(1,1)$ 开始，每次只能向右或向下移动，走到 $(n,m)$ 的最大得分为多少？

思路讲解

很容易想到动态规划。

设 $d{p}_{i,j,k}$ 为从 $(1,1)$ 走到 $(i,j)$，修改路径上 $k$ 个 ? 为 1 的最大得分，$s_{i,j}$ 为第 $i$ 行 $j$ 列的字符。

我们遍历 $i,j,k$，如果 $s_{i,j}$ 为 ?，且 $k>0$，则 $d{p}_{i,j,k}=\max (\max (d{p}_{i-1,j,k},d{p}_{i,j-1,k}),1+\max (d{p}_{i-1,j,k-1},d{p}_{i,j-1,k-1}))$，即我们改或者不改 $s_{i,j}$。

否则 $d{p}_{i,j,k}=[s_{i,j}=1]+\max (d{p}_{i-1,j,k},d{p}_{i,j-1,k})$

最终答案为 $\underset{i=0}{\overset{i\le x}{\max }}(d{p}_{n,m,i})$。

代码实现

#include <bits/stdc++.h>
using namespace std;
int t,n,m,x,dp[502][502][302];
string s[502];
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d%d%d",&n,&m,&x);
        for(int i=1;i<=n;i++){
            cin>>s[i];
            s[i]=" "+s[i];
        }
        memset(dp,0,sizeof(dp));//不要忘了初始化
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                for(int k=0;k<=x;k++){
                    dp[i][j][k]=(s[i][j]=='1')+max(dp[i-1][j][k],dp[i][j-1][k]);//先考虑不改变 s[i][j] 的情况
                    if(k>0 && s[i][j]=='?')
                        dp[i][j][k]=max(dp[i][j][k],1+max(dp[i-1][j][k-1],dp[i][j-1][k-1]));//考虑改变 s[i][j] 的情况
                }
        int ans=0;
        for(int i=0;i<=x;i++)
            ans=max(ans,dp[n][m][i]);//求最大值
        printf("%d\n",ans);
    }
    return 0;
}