描述 Description
windy 有 N 条木板需要被粉刷。 每条木板被分为 M 个格子。 每个格子要被刷成红色或蓝色。 windy 每次粉刷，只能选择一条木板上一段连续的格子，然后涂上一种颜色。 每个格子最多只能被粉刷一次。 如果 windy 只能粉刷 T 次，他最多能正确粉刷多少格子？ 一个格子如果未被粉刷或者被粉刷错颜色，就算错误粉刷。
输入格式 InputFormat
输入文件 paint.in 第一行包含三个整数，N M T。 接下来有 N 行，每行一个长度为 M 的字符串，’0’表示红色，’1’表示蓝色。
输出格式 OutputFormat
输出文件 paint.out 包含一个整数，最多能正确粉刷的格子数。
样例输入 SampleInput
3 6 3
111111
000000
001100
样例输出 SampleOutput
16
数据范围和注释 Hint
30% 的数据，满足 1 <= N,M <= 10 ； 0 <= T <= 100 。
100% 的数据，满足 1 <= N,M <= 50 ； 0 <= T <= 2500 。
代码 Code
二次动规。\(c[i,j,0..1]\) 表示：第 i 块板、前 j 个格子中 0 或 1 的个数。\(g[i,j,k]\) 表示：第 i 块板、粉刷 j 次、前 k 个格子、最多能粉刷正确的格子数。\(f[i,j]\) 表示：前 i 块板、粉刷 j 次、最多能粉刷正确的格子数。
\[ g[i,j,k]=Max \lbrace g[i,j-1,t]+Max \lbrace \begin{align} &c[i,k,0]-c[i,t,0] \\\\ &c[i,k,1],c[i,t,1] \end{align} \rbrace \rbrace,(0\leq t<k). \\\\ f[i,j]=Max \lbrace f[i-1,k]+g[i,j-k,m] \rbrace,(0\leq t \geq j). \]
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int inf=0x7fffffff;
int c[55][55][2],g[55][2505][55],f[55][2505];
int i,j,t,n,m,l,r,k,q,z,y,x;
char ch;
inline int cort(int s,int x,int y)
{
return max(c[s][y][0]-c[s][x-1][0],c[s][y][1]-c[s][x-1][1]);
}
int main()
{
memset(c,0,sizeof(c));
memset(f,-1,sizeof(f));
memset(g,0,sizeof(g));
scanf("%d%d%dn",&n,&m,&q);
if (n*m<=q)
{
printf("%dn",n*m);
return 0;
}
for (i=1;i<=n;i++)
{
for (j=1;j<=m;j++)
{
ch=getchar();
c[i][j][ch-'0']=c[i][j-1][ch-'0']+1;
c[i][j][(ch-'0')^1]=c[i][j-1][(ch-'0')^1];
}
ch=getchar();
}
f[0][0]=0;
for (i=1;i<=n;i++) for (j=1;j<=m;j++) for (k=1;k<=m;k++)
{
for (t=0;t<k;t++) g[i][j][k]=max(g[i][j][k],g[i][j-1][t]+cort(i,t+1,k));
}
for (i=1;i<=n;i++) for (j=0;j<=q;j++)
{
for (k=0;k<=j;k++) if (f[i-1][k]>=0) f[i][j]=max(f[i][j],f[i-1][k]+g[i][j-k][m]);
}
printf("%dn",f[n][q]);
return 0;
}