小鸟数据个人洛谷练习极简题解

P11242

碧树：叶子越远，枝干越长，已有的枝干再长一片叶子不影响枝干长度，最终就是枝干的长度加上叶子的总数。枝干总长取决于最远的那片叶子，叶子的总数题目中已经提供。

P11248

矩阵移动：三层循环，最内层循环k表示分别修改0、1、2、3...个问号时的最优解。

参考程序：

#include <bits/stdc++.h>
using namespace std;

int t,n,m,x,dp[505][505][505];
string s[505];

int main(){
    freopen("input.in","r",stdin);
    freopen("input.out","w",stdout);
    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]);
                    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]));
                    cout << dp[i][j][k];
                }
                //cout << endl;
            }
            cout << endl << endl;
        }

        int ans=0;
        for(int i=0;i<=x;i++)
            ans=max(ans,dp[n][m][i]);
        printf("%d\n",ans);
    }
    return 0;
}