题解 P4158 【[SCOI2009]粉刷匠】

# DP 前言:要明白"一个格子如果未被粉刷或者被粉刷错颜色，就算错误粉刷。"的含义(相当于全部粉刷(rank1的题解的0/1/2实属浪费)) #### 状态: f[ i ][ j ][ k ][ 0/1 ]: 1. 到达(i,j)时, 2. 用了k次刷子, 3. 这一格有没有刷对 #### 转移: 1. 换行时肯定要多刷一次 2. 若这一格与前一个格子颜色一样,最优的方式是把前一个的1状态原封不动转移,这时的0状态也跟着原封不动[算一个贪心]: ##### dp[i][j][k][1]=dp[i][j-1][k][1]+1; ##### dp[i][j][k][0]=dp[i][j-1][k][0]; 3. 否则[1]就有两个选择: (不要忘记我们设的[1]状态是强制这一格有贡献) 一个是牺牲一次k换种颜色刷,另一个是继续上一格的颜色 ##### dp[i][j][k][1]=max(dp[i][j-1][k-1][1]+1,dp[i][j-1][k][0]+1); 3.2.[0]也要贪心,因为这一格跟上一个不一样,所以如果要继续刷错,可能是从上一次[1]原封不动过来,可能是再用一刷使得刷错. ##### dp[i][j][k][0]=max(dp[i][j-1][k][1],dp[i][j-1][k-1][0]); 代码如下 ```cpp #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); // printf("dp[%d][%d][%d]=[0]%d [1]%d\n",i,j,k,dp[i][j][k][1],dp[i][j][k][2]); } cout<<ans; return 0; } ``` thanks