题目
题目描述: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; } //函数区