[SCOI2009]粉刷匠

(这dp,服了服了,...........额,没做出来,看题解会的)参考链接:https://www.luogu.com.cn/blog/GUO2002/solution-p4158
题解:涂色,对于每一行,要不全部都不会被涂色,要不全部都会被涂上色,涂错也算涂色,所以就不用考虑未涂色也算错误的因为涂色的颜色只有两种,所以就变成对于涂色的每一行,涂蓝色还是红色,然后dp, ,表示涂色到第i行,第j个位置,涂色k次,l=0/1,涂色正确或者错误的个数
然后涂色有三种情况:
(1)换行,对于每次换行后涂色,那铁定第一个位置是涂色正确的,那么可以得到


下来解释这个:涂错反过来看不就是涂对吗?
所以每次得到上述关系式
(2)对于不换行时,右边元素等于左边元素


正确值:左边那个元素涂色正确
错误值:不变
(3)对于不换行是,右边元素不等于左边元素
(3.1)正确值: 前面第j-1位涂k-1次的正确值+1,或者是前面j-1位涂k次的错误值+1
(3.2)错误值: 想要当前位错误,可以前面涂对的全部涂错,或者是当前位置涂对,(额,好怪.......)那么此时值可以为在j-1时k-1次涂错个数
然后每一次在涂色次数循环结束时,求最大值(最后写也行)
时间复杂度:
快绕蒙了...........

#include<bits/stdc++.h>
using namespace std;
int n,m,t,dp[51][51][51*51][2],co[51][51],ans;
int main(){
    cin>>n>>m>>t;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            char c=getchar();
            while(c!='0'&&c!='1')c=getchar();
            co[i][j]=c-'0';
        }
    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]);
                    dp[i][j][k][1]=max(dp[i-1][m][k-1][1],dp[i-1][m][k-1][0])+1;                    
                }else
                    if(co[i][j]==co[i][j-1]){
                        dp[i][j][k][1]=dp[i][j-1][k][1]+1;
                        dp[i][j][k][0]=dp[i][j-1][k][0];//贪心
                    }else{
                        dp[i][j][k][1]=max(dp[i][j-1][k-1][1]+1,dp[i][j-1][k][0]+1);
                        dp[i][j][k][0]=max(dp[i][j-1][k][1],dp[i][j-1][k-1][0]);
                    }
                ans=max(max(dp[i][j][k][0],dp[i][j][k][1]),ans);

            }
    cout<<ans;
    return 0;
}