1296: [SCOI2009]粉刷匠

Time Limit: 10 Sec Memory Limit: 162 MB

Submit: 2544 Solved: 1466

[Submit][Status][Discuss]

Description

windy有 N 条木板需要被粉刷。 每条木板被分为 M 个格子。 每个格子要被刷成红色或蓝色。 windy每次粉刷，只能选择一条木板上一段连续的格子，然后涂上一种颜色。 每个格子最多只能被粉刷一次。 如果windy只能粉刷 T 次，他最多能正确粉刷多少格子？ 一个格子如果未被粉刷或者被粉刷错颜色，就算错误粉刷。

Input

输入文件paint.in第一行包含三个整数，N M T。 接下来有N行，每行一个长度为M的字符串，’0’表示红色，’1’表示蓝色。

Output

输出文件paint.out包含一个整数，最多能正确粉刷的格子数。

Sample Input

3 6 3

111111

000000

001100

Sample Output

16

HINT

30%的数据，满足 1 <= N,M <= 10 ； 0 <= T <= 100 。 100%的数据，满足 1 <= N,M <= 50 ； 0 <= T <= 2500 。

题解

本蒟蒻不会什么太高深的做法，就猛写了一发毒瘤dp，莫名其妙过了dp[i][j][k][0/1/2]表示第i行第j列一共粉刷了k次，0/1/2分别表示当前格子没有涂色/涂了错的颜色/涂了对的颜色， 然后我们考虑逐格转移：当j=1也就是出于每行的第一个位置时，我们要考虑上一行的最后一个位置， 即dp[i][j][k][0]=max(dp[i-1][m][k][1],max(dp[i-1][m][k][2],dp[i-1][m][k][0]));dp[i][j][k][1]=max(dp[i-1][m][k-1][2],max(dp[i-1][m][k-1][1],dp[i-1][m][k-1][0]));dp[i][j][k][2]=max(dp[i-1][m][k-1][2],max(dp[i-1][m][k-1][1],dp[i-1][m][k-1][0]))+1;其余位置要考虑这个格子颜色是否和前一个格子的颜色相等，如果相等，就有dp[i][j][k][2]=dp[i][j-1][k][2]+1;可以直接接上dp[i][j][k][1]=max(dp[i][j-1][k][1],dp[i][j-1][k-1][0]);前面涂错或不涂 dp[i][j][k][0]=max(dp[i][j-1][k][0],dp[i][j-1][k][1]); 前面涂错或不涂如果不相等,dp[i][j][k][2]=max(dp[i][j-1][k-1][2],max(dp[i][j-1][k][1],dp[i][j-1][k-1][0]))+1;前面可能有三种情况dp[i][j][k][1]=max(dp[i][j-1][k][2],dp[i][j-1][k-1][0]);涂对或不涂       dp[i][j][k][0]=max(dp[i][j-1][k][0],dp[i][j-1][k][2]);涂对或不涂

可以用滚动数组压掉第一维，这样空间复杂度是O(nT),时间复杂度是O(nmT)，还是可以过的

代码

#include
    
     using namespace std;const int MAXN = 55;int n,m,t,dp[3][MAXN][2505][3]; bool col[MAXN][MAXN];int main(){    scanf("%d%d%d",&n,&m,&t);    for(register int i=1;i<=n;i++){        char c[MAXN];        scanf("%s",c+1);        for(register int j=1;j<=m;j++)            col[i][j]=c[j]-'0';    }    for(register int i=1;i<=n;i++)    for(register int j=1;j<=m;j++)    for(register int k=1;k<=t;k++){        if(j==1){            dp[i&1][j][k][0]=max(dp[(i-1)&1][m][k][1],dp[(i-1)&1][m][k][0]);            dp[i&1][j][k][0]=max(dp[i&1][j][k][0],dp[(i-1)&1][m][k][2]);            dp[i&1][j][k][1]=max(dp[(i-1)&1][m][k-1][1],dp[(i-1)&1][m][k-1][0]);            dp[i&1][j][k][1]=max(dp[i&1][j][k][1],dp[(i-1)&1][m][k-1][2]);            dp[i&1][j][k][2]=max(dp[(i-1)&1][m][k-1][1],dp[(i-1)&1][m][k-1][0])+1;            dp[i&1][j][k][2]=max(dp[i&1][j][k][2],dp[(i-1)&1][m][k-1][2]+1);        }         else{            if(col[i][j]==col[i][j-1]){                dp[i&1][j][k][2]=dp[i&1][j-1][k][2]+1;                dp[i&1][j][k][1]=max(dp[i&1][j-1][k][1],dp[i&1][j-1][k-1][0]);                dp[i&1][j][k][0]=max(dp[i&1][j-1][k][0],dp[i&1][j-1][k][1]);            }            else{                dp[i&1][j][k][2]=max(dp[i&1][j-1][k][1],dp[i&1][j-1][k-1][0])+1;                dp[i&1][j][k][2]=max(dp[i&1][j-1][k-1][2]+1,dp[i&1][j][k][2]);                dp[i&1][j][k][1]=max(dp[i&1][j-1][k][2],dp[i&1][j-1][k-1][0]);                dp[i&1][j][k][0]=max(dp[i&1][j-1][k][0],dp[i&1][j-1][k][2]);            }           }       //      cout<
     
      <<" "<
      
       <<" ";//      cout<
       
        <