粉刷匠（bzoj 1296）

Description

windy有 N 条木板需要被粉刷。 每条木板被分为 M 个格子。 每个格子要被刷成红色或蓝色。 windy每次粉刷，只能选择一条木板上一段连续的格子，然后涂上一种颜色。 每个格子最多只能被粉刷一次。 如果windy只能粉刷 T 次，他最多能正确粉刷多少格子？ 一个格子如果未被粉刷或者被粉刷错颜色，就算错误粉刷。

Input

输入文件paint.in第一行包含三个整数，N M T。 接下来有N行，每行一个长度为M的字符串，'0'表示红色，'1'表示蓝色。

Output

输出文件paint.out包含一个整数，最多能正确粉刷的格子数。

Sample Input

3 6 3
111111
000000
001100

Sample Output

16

HINT

30%的数据，满足 1 <= N,M <= 10 ； 0 <= T <= 100 。 100%的数据，满足 1 <= N,M <= 50 ； 0 <= T <= 2500 。

/*

    没想到scoi也有这么水的题。。。

    首先对于每个格子不管刷什么颜色，刷肯定比不刷更优，所以设

    dp[i][j][k][0/1]表示刷到i行j列用了k次并且这一格刷的是红/蓝的最大值。

    然后转移即可。

*/

#include<iostream>

#include<cstdio>

#define N 60

#define M 2510

using namespace std;

int dp[N][N][M][],n,m,T;

char a[N][N];

int main(){

    scanf("%d%d%d",&n,&m,&T);

    for(int i=;i<=n;i++) scanf("%s",a[i]+);

    for(int i=;i<=n;i++)

        for(int j=;j<=m;j++)

            for(int k=;k<=T;k++){

                if(j==){

                    dp[i][j][k][]=max(dp[i-][m][k-][],dp[i-][m][k-][])+(a[i][j]=='');

                    dp[i][j][k][]=max(dp[i-][m][k-][],dp[i-][m][k-][])+(a[i][j]=='');

                }

                else {

                    dp[i][j][k][]=max(dp[i][j-][k][],dp[i][j-][k-][])+(a[i][j]=='');

                    dp[i][j][k][]=max(dp[i][j-][k][],dp[i][j-][k-][])+(a[i][j]=='');

                }

            }

    int ans=;

    for(int i=;i<=T;i++)

        ans=max(ans,max(dp[n][m][i][],dp[n][m][i][]));

    printf("%d",ans);

    return ;

}