题目：http://www.lydsy.com/JudgeOnline/problem.php?id=1296
又是一道水水的DP，没什么好说的，直接上代码。
代码：
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std ;
#define rep( i , x ) for ( int i = 0 ; i ++ < x ; )
#define down( i , x ) for ( int i = x - 1 ; i >= 0 ; -- i )
const int maxn = 55 , maxt = 2550 ;
int n , m , t , f[ maxn ][ maxn ] , dp[ maxn ][ maxt ] ;
char s[ maxn ][ maxn ] ;
int main( ) {
scanf( "%d%d%d" , &n , &m , &t ) ;
rep( i , n ) scanf( "%s" , s[ i ] + 1 ) ;
memset( dp , 0 , sizeof( dp ) ) ;
rep( i , n ) {
memset( f , 0 , sizeof( f ) ) ;
rep( j , m ) rep( k , m ) {
f[ k ][ j ] = f[ k - 1 ][ j ] ;
int sum = s[ i ][ k ] - '0' ;
down( h , k ) {
f[ k ][ j ] = max( f[ k ][ j ] , f[ h ][ j - 1 ] + ( k - h ) - min( ( k - h ) - sum , sum ) ) ;
sum += s[ i ][ h ] - '0' ;
}
}
for ( int k = 0 ; k <= t ; ++ k ) dp[ i ][ k ] = dp[ i - 1 ][ k ] ;
rep( j , m ) {
int temp = 0 ;
rep( k , m ) temp = max( temp , f[ k ][ j ] ) ;
for ( int k = j ; k <= t ; ++ k ) {
dp[ i ][ k ] = max( dp[ i ][ k ] , dp[ i - 1 ][ k - j ] + temp ) ;
}
}
}
int ans = 0 ;
for ( int i = 0 ; i <= t ; ++ i ) ans = max( ans , dp[ n ][ i ] ) ;
printf( "%d\n" , ans ) ;
return 0 ;
}
