自动搬运

查看原文

来自洛谷，原作者为

	Vct14 **

搬运于2025-08-24 23:05:42，当前版本为作者最后更新于2024-11-08 20:23:55，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

upd：更新了滚动数组优化的内容。

考虑 dp。

设 $dp_{i,j,k}$ 表示当前走到了 $(i,j)$，已经改变 $k$ 个 ? 时的最多得分。

因为不需要恰好改变 $x$ 个 ?，所以我们每次从 $0$ 到 $x$ 遍历 $k$ 更新 $dp_{i,j,k}$。

首先有 $dp_{i,j,k}=\max(dp_{i-1,j,k},dp_{i,j-1,k})$，即从上面一格或左边一格一步过来。然后如果这一格上的字符为 1 那么 $dp_{i,j,k}$ 加一。

接下来就是如何处理 ?。按照上面的步骤，我们已经处理了 ? 不变的情况。那么如果要变，$dp_{i,j,k}=\max(dp_{i,j,k},\max(dp_{i-1,j,k-1},dp_{i,j-1,k-1})$。

最终答案为 $\max\limits_{k=0}^x dp_{n,m,k}$。

#include<bits/stdc++.h>
using namespace std;
#define dn dp[i][j][k]
const int N=502;

int dp[N][N][302];

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
    int t;cin>>t;
    while(t--){
        int n,m,x;cin>>n>>m>>x;
        memset(dp,0,sizeof(dp));
        for(int i=1; i<=n; i++){
        	for(int j=1; j<=m; j++){
				char a;cin>>a;
				for(int k=0; k<=x; k++){
		            dn=max(dp[i-1][j][k],dp[i][j-1][k])+(a=='1');
		            if(a=='?' && k) dn=max(dn,max(dp[i-1][j][k-1],dp[i][j-1][k-1])+1);
				}
			}
		}
        int mx=0;
        for(int k=0; k<=x; k++) mx=max(mx,dp[n][m][k]);
        cout<<mx<<"\n";
    }
    return 0;
}

注意到每一层的转移只与其上一层有关，因此可以使用滚动数组进行优化。

#include<bits/stdc++.h>
using namespace std;
#define dn dp[i%2][j][k]

int dp[2][502][302];

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
    int t;cin>>t;
    while(t--){
        int n,m,x;cin>>n>>m>>x;
        memset(dp,0,sizeof(dp));
        for(int i=1; i<=n; i++){
        	for(int j=1; j<=m; j++){
				char a;cin>>a;
				for(int k=0; k<=x; k++){
		            dn=max(dp[(i+1)%2][j][k],dp[i%2][j-1][k]);
		            if(a=='1') dn++;
		            if(a=='?' && k) dn=max(dn,max(dp[(i+1)%2][j][k-1],dp[i%2][j-1][k-1])+1);
				}
			}
		}
        int mx=0;
        for(int k=0; k<=x; k++) mx=max(mx,dp[n%2][m][k]);
        cout<<mx<<"\n";
    }
    return 0;
}