题解 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]);

代码如下

#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