BZOJ 1296（SCOI 2009）粉刷匠

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

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<bits/stdc++.h>

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<<dp[i][j][k][0]<<" "<<dp[i][j][k][1]<<" ";

//      cout<<dp[i][j][k][2]<<endl;

    }

    printf("%d",max(max(dp[n&1][m][t][0],dp[n&1][m][t][1]),dp[n&1][m][t][2]));

    return 0;

}

粉刷

BZOJ 1296（SCOI 2009） 粉刷匠

题解

代码

BZOJ 1296（SCOI 2009）粉刷匠