题目

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

输入描述:
第一行包含三个整数,N,M,T。
接下来有N行,每行一个长度为M的字符串,'0'表示红色,'1'表示蓝色。

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


解析

这道题的知识点当然一眼。。。两眼都没看出orz
  • 在借鉴了大佬的解析后我明白了这是个十分暴力的dp的写法

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

dp咋写???这里我们要讨论一下
  • 首先我们要分成三种情况:第一列的元素和前面数一样的数前面数不一样的数
  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;
    //i - 1表示上一行,M表示行尾元素,k - 1表示将这个位置涂色正确
    
    强调:我们在这里这样定义有点小特殊,1的意思是现在填的颜色和该位置要求相同,0表示不同。
  2. 然后是判断数是否和前面一样:你可能会在意为什么这个要判断?:因为如果相同的一笔画下去就好啦,不同的如果该位置要正确却要添加一笔
  3. 所以先判断和前面相同,我们的状态转移方程
    dp[i][j][k][0] = dp[i][j - 1][k][0];
    //现在的位置和前面一样(都是错误的),就直接继承就好啦
    dp[i][j][k][1] = dp[i][j - 1][k][1] + 1;
    //现在的位置和前面一样(都是正确的),就要在原来的大小上加上自己(+1)
  4. 最后判断和前面不同,我们的状态转移方程
    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)
    这里一个重要的点是我讲的:判断前面选错的多还是选对的多。为什么错的还要判断呢?
    因为我们一开始选择的是第一个点的颜色。所以如果我们换一个颜色,现在的错的不就变成对的了吗?

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


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;
}
//函数区