今天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种情况（第一种留到最后吧）。
a[i][j][k][0]=a[i][j-1][k][1]; a[i][j][k][1]=max(a[i][j-1][k][0],a[i][j-1][k-1][1])+1;
第一句的解释和上一个同理，我相信同学们不会把一个正确的颜色改成错误的。
但第二句就有2种可能性了，就像样例最后一行一样，全涂成红色反而最多，所以他要从保持上个颜色和换成正确的颜色之间选最大的一个。
然后就是第一种了，第一种就是继承上一行的最大可能性
a[i][j][k][0]=max(a[i-1][m][k-1][0],a[i-1][m][k-1][1]); a[i][j][k][1]=max(a[i-1][m][k-1][0],a[i-1][m][k-1][1])+1;
最大的地方就是上一行的最后一个了。可能他涂错颜色，总数大，也可能他涂对颜色，总数大。于是max一波（这个样例帮了我们大忙）
还有一个要注意的地方，截取最大值要从中间截取，至于为什么，你们可以把样例里的t换成2试试。（他最大能涂对12个，根本不用涂最后一块，照我这个写法就会错）。
好了，大家自己去试试吧。
感谢收看，感谢这个紫题，这是我第一个通过的紫题，我会记住这一天的（过几天就忘了）。