洛谷 P4158 [SCOI2009]粉刷匠题解

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

每日一题 day59 打卡

Analysis

很容易看出是一个dp，

dp[i][j[k][0/1]来表示到了(i,j)时，刷了k次，0表示这个没刷，1表示刷了。

于是有转移：

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);

4.0也要贪心,因为这一格跟上一个不一样,所以如果要继续刷错,可能是从上一次1原封不动过来,可能是再用一刷使得刷错.

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

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<queue>

 #define int long long

 #define rep(i,s,e) for(register int i=s;i<=e;++i)

 #define dwn(i,s,e) for(register int i=s;i>=e;--i)

 using namespace std;

 inline int read()

 {

     int x=,f=;

     char c=getchar();

     while(c<''||c>'') {if(c=='-') f=-; c=getchar();}

     while(c>=''&&c<='') {x=x*+c-''; c=getchar();}

     return f*x;

 }

 inline void write(int x)

 {

     if(x<) {putchar('-'); x=-x;}

     if(x>) write(x/);

     putchar(x%+'');

 }

 int n,m,t,ans;

 int map[][];

 int dp[][][][];

 signed main()

 {

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

     rep(i,,n)

         rep(j,,m)

         {

             char c=getchar();

             while(c!=''&&c!='') c=getchar();

             map[i][j]=c-'';

         }

     rep(i,,n)

         rep(j,,m)

             rep(k,,t)

             {

                 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(map[i][j]==map[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][])+;

                     }

                 }

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

             }

     write(ans);

     return ;

 }