Description
windy有 N 条木板需要被粉刷。
每条木板被分为 M 个格子。
每个格子要被刷成红色或蓝色。
windy每次粉刷，只能选择一条木板上一段连续的格子，然后涂上一种颜色。
每个格子最多只能被粉刷一次。
如果windy只能粉刷 T 次，他最多能正确粉刷多少格子？
一个格子如果未被粉刷或者被粉刷错颜色，就算错误粉刷。
每条木板被分为 M 个格子。
每个格子要被刷成红色或蓝色。
windy每次粉刷，只能选择一条木板上一段连续的格子，然后涂上一种颜色。
每个格子最多只能被粉刷一次。
如果windy只能粉刷 T 次，他最多能正确粉刷多少格子？
一个格子如果未被粉刷或者被粉刷错颜色，就算错误粉刷。
Input
第一行包含三个整数，N M T。
接下来有N行，每行一个长度为M的字符串，'0'表示红色，'1'表示蓝色。
接下来有N行，每行一个长度为M的字符串，'0'表示红色，'1'表示蓝色。
Output
输出一个整数，表示最多能正确粉刷的格子数。
Sample Input
3 6 3
111111
000000
001100
Sample Output
16
Data Constraint
Hint
100%的数据，满足 1 <= N,M <= 50 ； 0 <= T <= 2500 。
这道题很显然是一道动态规划题，但是我们发现，如果我们想用一个动态规划去做这道题，那么状态和转移都会十分的麻烦，这时候我们就要想是否需要两个动态规划来完成一个复杂的过程，我们看到这道题如果只问每一行的最优结果，那么转移就会很简单，所以我们可不可以将这个问题转化成先求每一行粉刷k次的最优解再求前i行操作k次的最优解。
既然思路确定，那么我们就可以设状态了：1-设置g数组表示在第i行，粉刷j次，刷到k的最优解，2-设置f表示前i行，刷j次的最优解。
转移方程也很好写：1- g[i][j][k]=max(g[i][j][k],max(用前缀和计算在p到k之间最多可以有多少正确的)+g[i][j-1][p]); p是从j-1开始枚举的，具体为什么代码上有注释，k是从j开始的，因为j进行了j次粉刷后最少粉刷到j点。
关于f的是 f[i][j]=max(f[i-1][j-k]+g[i][k][m]).
下面上代码：
#include<iostream>
#include<cstdio>
using namespace std;
int f[][],sum[][]; //f表示前i行刷j次最大对值。
int g[][][]; //第i行，刷到第j个用k次粉刷得到的最大对值。
int n,m,t;
char s[];
int main(){
ios::sync_with_stdio();
cin>>n>>m>>t;
for(int i=;i<=n;i++){
cin>>s;
sum[i][]=;
for(int j=;j<=m;j++){
if(s[j-]=='') sum[i][j]=sum[i][j-]+;
else sum[i][j]=sum[i][j-];
}
}
for(int i=;i<=n;i++){
for(int j=;j<=m;j++){
for(int k=j;k<=m;k++){
for(int p=j-;p<k;p++){ //因为q是第j-1次粉刷，每一次粉刷至少一格，所以q最少为j-1.
g[i][j][k]=max(g[i][j][k],max(sum[i][k]-sum[i][p],k-p-sum[i][k]+sum[i][p])+g[i][j-][p]);
}
}
}
}
for(int i=;i<=n;i++){
for(int j=;j<=t;j++){
for(int k=;k<=min(j,m);k++){
f[i][j]=max(f[i][j],f[i-][j-k]+g[i][k][m]);
}
}
}
int ans=;
for(int i=;i<=t;i++){
ans=max(ans,f[n][i]);
}
cout<<ans;
}