粉刷匠

题目描述
windy有 N 条木板需要被粉刷。 每条木板被分为 M 个格子。 每个格子要被刷成红色或蓝色。
windy每次粉刷，只能选择一条木板上一段连续的格子，然后涂上一种颜色。 每个格子最多只能被粉刷一次。
如果windy只能粉刷 T 次，他最多能正确粉刷多少格子？
一个格子如果未被粉刷或者被粉刷错颜色，就算错误粉刷。
输入描述:
第一行包含三个整数，N M T。
接下来有N行，每行一个长度为M的字符串，'0'表示红色，'1'表示蓝色。
30%的数据，满足 1 <= N,M <= 10 ； 0 <= T <= 100 。
100%的数据，满足 1 <= N,M <= 50 ； 0 <= T <= 2500 。
输出描述:
输出包含一个整数，最多能正确粉刷的格子数。

思路：

如果是每条木板的第一段，那么肯定是由上一条木板的结尾转移过来，这里注意肯定要进行新的一次涂色，所以转移方程为


表示从上一条木板的最后一段转移过来，是选择什么颜色以及当前位置颜色是否涂对

如果不是每条木板的第一段，那么肯定是由该条木板的前一段转移过来


表示当前位置要涂0，那么选择上一段涂0的，涂的次数就不变，选择上一段涂1的那么次数肯定是比上次多一次，在加上该位置是否正确
当前位置涂1，那么选择上一段涂1的，涂的次数不变，选择上一段涂0的，次数比上一次多1，加上该位置是否涂正确。

#include<bits/stdc++.h>
using namespace std;
char mp[55][55];
int dp[55][55][2555][2];///前i条j段涂k次 最后一段涂红/蓝的最多正确格子数
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++)
    {
        for(int j=1; j<=m; 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]);

    return 0;
}