P11248 [GESP202409 七级] 矩阵移动

Koei · 2025-10-03 21:33:42 · 算法·理论

把DP写在脸上的一道题

状态：dp_{i,j,k}

表示位置为(i,j)且还可以转换k个?时的最大得分

状态转移方程：

1. 当(i,j)是1时：dp_{i,j,k}=max(dp_{i-1,j,k},dp_{i,j-1,k})+1
2. 当(i,j)是0时：dp_{i,j,k}=max(dp_{i-1,j,k},dp_{i,j-1,k})
3. 当(i,j)是?时：dp_{i,j,k}=max(dp_{i,j,k},max(dp_{i-1,j,k-1},dp_{i,j-1,k-1})+1) 前提是 k>0

至于为什么会TLE，只能说这题卡常，太缺德了

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn(5e2+10);
int T,n,m,x;
int dp[maxn][maxn][maxn];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>T;
    while(T--){
        int maxx(0);
        cin>>n>>m>>x;
        memset(dp,0,sizeof(dp));
        for(int i(1);i<=n;++i){
            for(int j(1);j<=m;++j){
                char ch;
                cin>>ch;
                for(int k(0);k<=x;++k){
                    dp[i][j][k]=max(dp[i-1][j][k],dp[i][j-1][k])+(ch=='1');
                    if(k&&ch=='?'){
                        dp[i][j][k]=max(dp[i][j][k],max(dp[i-1][j][k-1],dp[i][j-1][k-1])+1);
                    }
                }
            }
        }
        for(int k(0);k<=x;++k){
            maxx=max(maxx,dp[n][m][k]);
        }
        // printf("%d\n",maxx);
        cout<<maxx<<'\n';
    }
    return 0;
}