[Bzoj1296][Scoi2009] 粉刷匠 [DP + 分组背包]

1296: [SCOI2009]粉刷匠

Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 2184 Solved: 1259
[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

Sample Output

HINT

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

分析：

对于每一块版子粉刷时是互不相干的，所以每一块是单独求的。

先n^4处理出每一块版子的dp数组，dp[q][i][x]表示第q块版子，前x个位置粉刷i次的最大值。

因为每一块版子单独处理，可以省掉一维变成dp[i][x]

转移方程为： dp[i][x] = max(dp[i][x],dp[i - 1][y] + max(blue[q][x] - blue[q][y],red[q][x] - red[q][y]));

然后做分组背包处理f[i][j]，表示前i块版子，粉刷j次的最大值

转移方程为： f[q][i] = max(f[q][i],f[q - 1][i - j] + dp[j][m]);

求出f[n][i]中最大值即为答案；

贴上AC代码：

# include <iostream>

# include <cstdio>

# include <cstring>

using namespace std;

char str[][];

int dp[][];

int blue[][],red[][];

int f[][];

int n,m,t;

int main(){

scanf("%d %d %d",&n,&m,&t);

for(int i = ;i <= n;i++){

    scanf("%s",&str[i][]);

}

for(int i = ;i <= n;i++){

    for(int j = ;j <= m;j++){

        blue[i][j] = blue[i][j - ];

        red[i][j]  = red[i][j - ];

        if(str[i][j] == '')blue[i][j]++;

        else red[i][j]++;

    }

}

for(int q = ; q <= n;q++){

    memset(dp,,sizeof dp);

      for(int i = ;i <= min(t,m);i++){

          for(int x = ;x <= m;x++){

              for(int y = ;y < x;y++){

                  dp[i][x] = max(dp[i][x],dp[i - ][y] + max(blue[q][x] - blue[q][y],red[q][x] - red[q][y]));

              }

          }

      }

    for(int i = ;i <= t;i++){

        for(int j = ;j <= min(i,m);j++){

            f[q][i] = max(f[q][i],f[q - ][i - j] + dp[j][m]);

        }

    }

}

int ans = ;

for(int i = ;i <= t;i++)ans = max(ans,f[n][i]);

printf("%d\n",ans);

  return ;

}

巴特西