洛谷P4158 [SCOI2009]粉刷匠

传送门

设$dp[i][j][k][0/1]$表示在涂点$(i,j)$，涂了$k$次，当前点的颜色是否对，最多能刷对多少个格子

首先换行的时候肯定得多刷一次

然后是如果和前一个格子颜色相同，那么当前点是否刷对都要转移

如果和前一个格子颜色不相同，那么就考虑是否要再刷一次还是直接转移

 //minamoto

 #include<iostream>

 #include<cstdio>

 using namespace std;

 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)

 char buf[<<],*p1=buf,*p2=buf;

 template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,:;}

 int read(){

     #define num ch-'0'

     char ch;bool flag=;int res;

     while(!isdigit(ch=getc()))

     (ch=='-')&&(flag=true);

     for(res=num;isdigit(ch=getc());res=res*+num);

     (flag)&&(res=-res);

     #undef num

     return res;

 }

 const int N=;

 int n,m,t,dp[N][N][N*N][],col[N][N],ans;

 int main(){

 //    freopen("testdata.in","r",stdin);

     n=read(),m=read(),t=read();

     for(int i=;i<=n;++i) for(int j=;j<=m;++j){

         char ch;while((ch=getc())!=''&&ch!='');

         col[i][j]=ch-'';

     }

     for(int i=;i<=n;++i) for(int j=;j<=m;++j) for(int k=;k<=t;++k){

         if(j==){

             dp[i][j][k][]=max(dp[i-][m][k-][],dp[i-][m][k-][]);

             dp[i][j][k][]=max(dp[i-][m][k-][],dp[i-][m][k-][])+;

         }else{

             if(col[i][j]==col[i][j-]){

                 dp[i][j][k][]=dp[i][j-][k][]+;

                 dp[i][j][k][]=dp[i][j-][k][];

             }else{

                 dp[i][j][k][]=max(dp[i][j-][k-][]+,dp[i][j-][k][]+);

                 dp[i][j][k][]=max(dp[i][j-][k][],dp[i][j-][k-][]);

             }

         }cmax(ans,max(dp[i][j][k][],dp[i][j][k][]));

     }

     printf("%d\n",ans);

     return ;

 }