题目大意
给出一个
n
n
n 行
m
m
m 列的只包含 0、1、? 的矩阵，你可以选择至多
x
x
x 个 ? 改成 1。
设得分为经过的 1 的数量，求从矩阵的
(
1
,
1
)
(1,1)
(1,1) 开始，每次只能向右或向下移动，走到
(
n
,
m
)
(n,m)
(n,m) 的最大得分为多少？
思路讲解
很容易想到动态规划。
设
d
p
i
,
j
,
k
dp_{i,j,k}
dpi,j,k 为从
(
1
,
1
)
(1,1)
(1,1) 走到
(
i
,
j
)
(i,j)
(i,j)，修改路径上
k
k
k 个 ? 为 1 的最大得分，
s
i
,
j
s_{i,j}
si,j 为第
i
i
i 行
j
j
j 列的字符。
我们遍历
i
,
j
,
k
i,j,k
i,j,k，如果
s
i
,
j
s_{i,j}
si,j 为 ?，且
k
>
0
k>0
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
)
)
dp_{i,j,k}=\max(\max(dp_{i-1,j,k},dp_{i,j-1,k}),1+\max(dp_{i-1,j,k-1},dp_{i,j-1,k-1}))
dpi,j,k=max(max(dpi−1,j,k,dpi,j−1,k),1+max(dpi−1,j,k−1,dpi,j−1,k−1))，即我们改或者不改
s
i
,
j
s_{i,j}
si,j。
否则 d p i , j , k = [ s i , j = 1 ] + max ( d p i − 1 , j , k , d p i , j − 1 , k ) dp_{i,j,k}=[s_{i,j}=1]+\max(dp_{i-1,j,k},dp_{i,j-1,k}) dpi,j,k=[si,j=1]+max(dpi−1,j,k,dpi,j−1,k)
最终答案为 max i = 0 i ≤ x ( d p n , m , i ) \max\limits_{i=0}^{i\le x}(dp_{n,m,i}) i=0maxi≤x(dpn,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;
}