题解：P11248 [GESP202409 七级] 矩阵移动

Vct14 · 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;
}