题目传送门
题目大意
给出一个 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;
}