今天A了个紫（我膨胀了），他看起来像个贪心一样，老师说我写的是dp（dp理解不深的缘故QWQ）
直接放题目描述（我旁边有个家伙让我放链接，我还是说明出处吧（万一出处没有了）我讲的大多数题目都是出自洛谷，大佬们有兴趣可以去水一下。
题目描述 windy有 N 条木板需要被粉刷。 每条木板被分为 M 个格子。 每个格子要被刷成红色或蓝色。 windy每次粉刷，只能选择一条木板上一段连续的格子，然后涂上一种颜色。 每个格子最多只能被粉刷一次。 如果windy只能粉刷 T 次，他最多能正确粉刷多少格子？ 一个格子如果未被粉刷或者被粉刷错颜色，就算错误粉刷。 输入格式 第一行包含三个整数，N M T。 接下来有N行，每行一个长度为M的字符串，‘0‘表示红色，‘1‘表示蓝色。 输出格式 包含一个整数，最多能正确粉刷的格子数。 输入输出样例 输入 #1复制 3 6 3 111111 000000 001100 输出 #1复制 16 说明/提示 30%的数据，满足 1 <= N,M <= 10 ； 0 <= T <= 100 。 100%的数据，满足 1 <= N,M <= 50 ； 0 <= T <= 2500 。
这个题看起来是个贪心的样子呢，我们来水一下吧。
有个大佬说过:dp不会加一维。
因为空间够，所以我开了4维数组（空间竟然没爆）。a[i][j][k][0/1]的4个维度分别是现在的位置是(i,j)，k是现在的步数，第4维有2种：0是涂色错误，1是涂色正确。a[i][j][k][0/1]的值是到达这种情况的最大值。（看着没毛病，妥妥的暴力）
首先这个题有3种情况。
1：现在的状态处于一块木板的开头。
2：现在的字符和上一个字符相符。
3：现在的字符和上一个字符不符。
如果1是成立的，那2，3就可以不管了。
现在把这道题分成3部分来做。
首先是第2部分（第2部分很简单的）
a[i][j][k][0]=a[i][j-1][k][0]; a[i][j][k][1]=a[i][j-1][k][1]+1;
有的同学可能有个疑问，为什么第二句不是下方代码呢？
a[i][j][k][1]=max(a[i][j-1][k][1],a[i][j-1][k-1][0])+1;
我来解释一下，第二种情况是他和前一个相符的，竟然这样，那直接从刚开始不同的地方更改不是更香吗？（真香）
（我相信不会有哪个人把正确的颜色改成错误的，所以这个情况就结束了……）
所以现在我们就把第二种情况解决了（真草率）。开始处理第3种情况（第一种留到最后吧）。
未完待续……
原文：https://www.cnblogs.com/lichangjian/p/13086080.html