P11248 [GESP202409 七级] 矩阵移动

把DP写在脸上的一道题

状态：

dp_{i,j,k}

表示位置为

(i,j)

且还可以转换

k

个

?

时的最大得分

状态转移方程：

当 $(i,j)$ 是1时： $dp_{i,j,k}=max(dp_{i-1,j,k},dp_{i,j-1,k})+1$
当 $(i,j)$ 是0时： $dp_{i,j,k}=max(dp_{i-1,j,k},dp_{i,j-1,k})$
当 $(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，只能说这题卡常，~~太缺德了~~

CPP

#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;
}

P11248 [GESP202409 七级] 矩阵移动

文章操作

相关推荐

评论

P11248 [GESP202409 七级] 矩阵移动