一.闲话

五一收假了，qwq好气哦

二.题解

终于做到原题了（雾）

这次就是一个比较简单的dp，只是状态的复杂度。。。（请参考传纸条）

我们设dp[i][j][k][0/1]表示已刷完i-1个木块，第i个木块我们刷了前j个格子，第j个格子是否刷成符合我们需求的颜色,我们一共刷了k次所能获得的

不难发现，我们尽量剩余次数越多，越容易，所以，能一次完成的我们就一次刷完。

于是，对于每个格子我们有讨论:

如果左边格子刷的颜色和当前格子刷的颜色相同，k不变直接转移过来

否则，我们直接重新开始刷一次，则从左边格子的k-1转移过来

注意判断边界条件，也就是j=1的时候，这时，所有转移都来着上个木板，所以，我们必须直接从上个木块的k-1转移过来，即可

代码:

#include<bits/stdc++.h>
using namespace std;
const int N=51,T=2501;
int dp[N][N][T][2],a[N][N];
int main(){
    int n,m,t;
    scanf("%d%d%d",&n,&m,&t);
    if(!t){
        puts("0");
        return 0;
    }
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            scanf("%1d",&a[i][j]);
        }
    }
    dp[1][1][1][1]=1,dp[1][1][0][0]=0;
    int ans=1; 
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            for(int k=1;k<=t;++k){
                if(i==1&&j==1){
                    continue;
                }
                if(j==1){
                    dp[i][j][k][1]=max(dp[i-1][m][k-1][1],dp[i-1][m][k-1][0])+1;
                    dp[i][j][k][0]=max(dp[i-1][m][k-1][1],dp[i-1][m][k-1][0]);
                    ans=max(ans,max(dp[i][j][k][1],dp[i][j][k][0]));
                    continue;
                }
                if(a[i][j]==a[i][j-1]){
                    dp[i][j][k][1]=max(dp[i][j-1][k-1][0],dp[i][j-1][k][1])+1;
                    dp[i][j][k][0]=max(dp[i][j-1][k-1][1],dp[i][j-1][k][0]);
                }
                else{
                    dp[i][j][k][1]=max(dp[i][j][k][1],max(dp[i][j-1][k][0],dp[i][j-1][k-1][1])+1);
                    dp[i][j][k][0]=max(dp[i][j][k][0],max(dp[i][j-1][k][1],dp[i][j-1][k-1][0]));
                }
                ans=max(ans,max(dp[i][j][k][1],dp[i][j][k][0]));
            }
        }
    }
    printf("%d",ans);
    return 0;
}