先考虑一块木板的情况：
每个格子只能被粉刷一次，所以不用考虑覆盖的问题，大可从前往后顺序粉刷。
令 \(f_{i, j}\) 表示前 \(i\) 个格子涂 \(j\) 次最多能粉刷正确的格子数，则可以得到转移方程：
\[f_{i, j} = \max_{1 \le k < i}\{f_{k, j – 1} + \max\{\text{Red}(k + 1, i), \text{Blue}(k + 1, i)\}\} \]
其中 \(\text{Red}(x, y)\) 表示区间 \([x, y]\) 内应该涂成红色的格子数，\(\text{Blue}(x, y)\) 表示区间 \([x, y]\) 内应该涂成蓝色的格子数。
\(\text{Red}(x, y)\) 和 \(\text{Blue}(x, y)\) 该如何维护？
用前缀和维护区间和即可。
推广到多块木板：
我们还是对每块木板求一遍 \(f_{i, j}\)，即求出 \(f_{i, j, k}\) 表示第 \(i\) 块木板的前 \(j\) 个格子涂 \(k\) 次最多能正确粉刷的格子数。
类似地，令 \(F_{i, j}\) 表示前 \(i\) 块木板涂 \(j\) 次最多能粉刷正确的格子数，则又可以得到转移方程：
\[F_{i, j} = \max_{0 \le k < j}\{F_{i – 1, k} + f_{i, M, j – k}\} \]
最后的答案就是 \(F_{N, T}\)。
可以通过改变枚举顺序优化空间复杂度（不优化也无所谓）。
$\text{Code}$
#include <bits/stdc++.h>
#define MAXN 60
#define MAXT 2600
using namespace std;
int n, m, t;
int sum0[MAXN], sum1[MAXN], f[MAXN][MAXT], F[MAXT];
char s[MAXN];
template<typename _T>
void read(_T &_x) {
_x = 0;
_T _f = 1;
char _ch = getchar();
while (_ch < '0' || '9' < _ch) {
if (_ch == '-') _f = -1;
_ch = getchar();
}
while ('0' <= _ch && _ch <= '9') {
_x = (_x << 3) + (_x << 1) + (_ch & 15);
_ch = getchar();
}
_x *= _f;
}
template<typename _T>
void write(_T _x) {
if (_x < 0) {
putchar('-');
_x = -_x;
}
if (_x > 9) write(_x / 10);
putchar('0' + _x % 10);
}
int main() {
read(n), read(m), read(t);
while (n--) {
scanf("%s", s + 1);
memset(f, 0, sizeof(f));
for (int i = 1; i <= m; i++) {
sum0[i] = sum0[i - 1] + (s[i] == '0');
sum1[i] = sum1[i - 1] + (s[i] == '1');
for (int j = 1; j <= t; j++) {
for (int k = j - 1; k < i; k++) {
f[i][j] = max(f[i][j], f[k][j - 1] + max(sum0[i] - sum0[k], sum1[i] - sum1[k]));
}
}
}
for (int i = t; i; i--) {
for (int j = 0; j < i; j++) {
F[i] = max(F[i], F[j] + f[m][i - j]);
}
}
}
write(F[t]);
return 0;
}
原文地址：http://www.cnblogs.com/chy12321/p/16879991.html
1. 本站所有资源来源于用户上传和网络，如有侵权请邮件联系站长！
2. 分享目的仅供大家学习和交流，请务用于商业用途!
3. 如果你也有好源码或者教程，可以到用户中心发布，分享有积分奖励和额外收入！
4. 本站提供的源码、模板、插件等等其他资源，都不包含技术服务请大家谅解！
5. 如有链接无法下载、失效或广告，请联系管理员处理！
6. 本站资源售价只是赞助，收取费用仅维持本站的日常运营所需！
7. 如遇到加密压缩包，默认解压密码为"gltf",如遇到无法解压的请联系管理员！
8. 因为资源和程序源码均为可复制品，所以不支持任何理由的退款兑现，请斟酌后支付下载
声明：如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性
