BZOJ-1296: [SCOI2009]粉刷匠(dp)

题目：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 ;
}