【每日一题】粉刷匠

[SCOI2009]粉刷匠

https://ac.nowcoder.com/acm/problem/20273

题目

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

一个格子如果未被粉刷或者被粉刷错颜色，就算错误粉刷。

输入描述：
第一行包含三个整数，N，M，T。

接下来有N行，每行一个长度为M的字符串，'0'表示红色，'1'表示蓝色。

输出描述：
包含一个整数，表示最多能正确粉刷的格子数。

解析

这道题的知识点当然一眼。。。两眼都没看出orz

在借鉴了大佬的解析后我明白了这是个十分暴力的dp的写法。

算法解析：（以下均用01代表颜色）

根据题目，我们可以认为这就是个二维数组，首先我们要知道一个前提：我们一定会把每行画满。
为啥一定会画满呢？因为我们结果是要画对的最大数，也就是说，你画错了没事，那你不画满干嘛嘞你说是吧~
接下来就是我们最奇妙的dp数组咋整了。因为题目是个二维数组，然后还要考虑到你笔画的次数，所以我们定义为dp[MAX][MAX][MAX * MAX][2]。
这里的dp的含义是：dp[行][列][涂色次数][该点是否正确] = 到现在的涂色正确数。也就是某一个位置在某一个颜色、某一次涂色时，最大的涂色正确数。
其实在知道这一步的时候我们大概就已经清楚了。（详细看下面dp板块）

dp咋写？？？这里我们要讨论一下

首先我们要分成三种情况：第一列的元素；和前面数一样的数；和前面数不一样的数；

首先是第一列元素，第一列元素有什么特别的大家都能想到：因为第一列元素是接着上一列列尾元素的；
我们就能得到我们状态转移方程：
```
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][0], dp[i - 1][M][k - 1][1]) + 1;
//i - 1表示上一行，M表示行尾元素，k - 1表示将这个位置涂色正确
```
强调：我们在这里这样定义有点小特殊，1的意思是现在填的颜色和该位置要求相同，0表示不同。
然后是判断数是否和前面一样：你可能会在意为什么这个要判断？：因为如果相同的一笔画下去就好啦，不同的如果该位置要正确却要添加一笔。

所以先判断和前面相同，我们的状态转移方程：

dp[i][j][k][0] = dp[i][j - 1][k][0];
//现在的位置和前面一样（都是错误的），就直接继承就好啦
dp[i][j][k][1] = dp[i][j - 1][k][1] + 1;
//现在的位置和前面一样（都是正确的），就要在原来的大小上加上自己（+1）

最后判断和前面不同，我们的状态转移方程：

dp[i][j][k][0] = max(dp[i][j - 1][k - 1][0], dp[i][j - 1][k][1]);
//现在的位置是错的，上一个位置是正确的，所以判断前面选错的多还是选对的多
dp[i][j][k][1] = max(dp[i][j - 1][k][0], dp[i][j - 1][k - 1][1]) + 1;
//现在的位置是对的，上一个位置是错的，一样要判断前面错的多还是对的多，然后加上自己（+1）

这里一个重要的点是我讲的：判断前面选错的多还是选对的多。为什么错的还要判断呢？
因为我们一开始选择的是第一个点的颜色。所以如果我们换一个颜色，现在的错的不就变成对的了吗？

终于可以打代码了：

没问题，先把该存的存下来，有点小麻烦的是我们存的是字符串，因为他没给空格。但是大家肯定都会（不会也可以看我代码）。
然后一顿dp过去，三层循环。（学了这么久看过的最暴力的dp）。
最后输出就好了，选出最大的。这里我们不需要三层循环来找，因为后面会继承前面的（这样可以省很多时间哦）。
所以在最后一行，笔画上限里面选出最大值就好了。
看我代码吧~我话真多哈哈哈

AC代码

#include <iostream>
using namespace std;
//代码预处理区

const int MAX = 50 + 7;
int mp[MAX][MAX];//输入的涂色要求表
int dp[MAX][MAX][MAX * MAX][2];//dp[行][列][涂色次数][该点是否正确] = 到现在的涂色正确数
//全局变量区

int main() {
    int N, M, T; scanf("%d %d %d", &N, &M, &T);
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= M; j++) {
            char ch = getchar();
            while (ch != '0' && ch != '1') ch = getchar();
            mp[i][j] = ch - '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][0], dp[i - 1][M][k - 1][1]) + 1;
                    //特判：第一列接上一列行尾
                }
                else if (mp[i][j] == mp[i][j - 1]) {
                    dp[i][j][k][0] = dp[i][j - 1][k][0];
                    dp[i][j][k][1] = dp[i][j - 1][k][1] + 1;
                    //相邻相同判断（继承上一点）
                }
                else {
                    dp[i][j][k][0] = max(dp[i][j - 1][k - 1][0], dp[i][j - 1][k][1]);
                    dp[i][j][k][1] = max(dp[i][j - 1][k][0], dp[i][j - 1][k - 1][1]) + 1;
                    //相邻不同判断（判断前面涂哪种颜色正确的多）
                }
    int ans = 0;
    for (int j = 1; j <= M; j++)
        ans = max(ans, max(dp[N][j][T][0], dp[N][j][T][1]));
    //选出最大值（因为后面会包含前面的大小，判断最后一行即可）
    printf("%d\n", ans);
    return 0;
}
//函数区

每日一题文章被收录于专栏

憨憨的专栏