[SCOI2009]粉刷匠（dp）

参考题解

题意：略。

题记：dp[i][j][k][0/1]表示为前i条j段涂k次，最后一段涂红/蓝的最多正确格子数。

可以理解为将所有木条分成了n*m的木块。然后一块一块地填。
那么可以分成两种情况：
1、当前木块是整条木板的第一块，一定要进行一次新的涂色。（即j为1的情况）
由上一条木条的最后一块木板转移过来

当前木块涂红色：dp[i][j][k][0]=max(dp[i−1][m][k−1][0],dp[i−1][m][k−1][1])+(mp[i][j]==0);

当前木块涂蓝色：dp[i][j][k][1]=max(dp[i−1][m][k−1][0],dp[i−1][m][k−1][1])+(mp[i][j]==1);

2、当前木块不是整条木板的第一块，根据前一块木块的颜色来
判断是否需要新的涂色。（即j不为1的情况）
由同一条木条的前一块木板转移过来

当前木块涂红色：dp[i][j][k][0]=max(dp[i][j−1][k][0],dp[i][j−1][k−1][1])+(mp[i][j]==0);

当前木块涂蓝色：dp[i][j][k][1]=max(dp[i][j−1][k][1],dp[i][j−1][k−1][0])+(mp[i][j]==1);

#include<bits/stdc++.h>

using namespace std;
const int N=55;
char mp[N][N];
int dp[N][N][2510][2];//dp[i][j][k][0/1]
//前i条j段涂k次，最后一段涂红/蓝的最多正确格子数
//红（0）蓝（1）
int main(){
    int n,m,t;
    cin>>n>>m>>t;
    for(int i=1;i<=n;i++)
        cin>>mp[i]+1;
    for(int i=1;i<=n;i++){//枚举第i条木板
        for(int j=1;j<=m;j++){//枚举第j段
            for(int k=1;k<=t;k++){//枚举涂的次数
                if(j==1){
                    dp[i][j][k][0]=max(dp[i-1][m][k-1][0],dp[i-1][m][k-1][1])+(mp[i][j]=='0');
                    dp[i][j][k][1]=max(dp[i-1][m][k-1][0],dp[i-1][m][k-1][1])+(mp[i][j]=='1');
                }
                else{
                    dp[i][j][k][0]=max(dp[i][j-1][k][0],dp[i][j-1][k-1][1])+(mp[i][j]=='0');
                    dp[i][j][k][1]=max(dp[i][j-1][k][1],dp[i][j-1][k-1][0])+(mp[i][j]=='1');
                }
            }
        }
    }
    cout<<max(dp[n][m][t][0],dp[n][m][t][1])<<endl;
    return 0;
}