BZOJ 1296: [SCOI]粉刷匠( dp )

dp[ i ][ j ] = max( dp[ i - 1 ][ k ] + w[ i ][ j - k ] ) ( 0 <= k <= j ) 表示前 i 行用了 j 次粉刷的机会能正确粉刷的格子数 , 状态的转移很显然 , w[ i ][ j ] 表示 第 i 行使用 j 次粉刷机会能正确粉刷的格子数.

接下来考虑 w , 对于每一行 : DP[ i ][ j ] = max( DP[ k ][ j - 1 ] + sum( k + 1 , i )) ( 0 <= k < i ) sum( l , r ) 表示从区间[ l , r ] 的颜色相同的格子的个数的较大值( 因为两种颜色 ) , 那么 w[ i ][ j ] = 对第 i 行做的 DP[ m ][ j ] .

---------------------------------------------------------------------------------------------

#include<cstdio>#include<cstring>#include<algorithm>#include<vector>#include<iostream>#define rep( i , n ) for( int i = 0 ; i < n ; ++i )#define clr( x , c ) memset( x , c , sizeof( x ) )#define Rep( i , n ) for( int i = 1 ; i <= n ; ++i )using namespace std;const int maxn = 50 + 5;const int maxt = 2500 + 5;int sum[ maxn ][ maxn ];int n , m , T;int w[ maxn ][ maxt ];int D[ maxn ][ maxt ];int d[ maxn ][ maxt ];int cur;int Dp( int x , int k ) {int &ans = D[ x ][ k ];if( ans != -1 ) return ans;ans = 0;rep( i , x ) {int t = sum[ cur ][ x ] - sum[ cur ][ i ]; ans = max( ans , Dp( i , k - 1 ) + max( t , x - i - t ) );}return ans;}void init() {clr( w , 0 );Rep( i , n ) {clr( D , -1 );rep( j , T + 1 ) D[ 0 ][ j ] = 0;Rep( j , m ) D[ j ][ 0 ] = 0; Rep( j , T ) w[ cur = i ][ j ] = Dp( m , j );}}int dp( int x , int k ) {int &ans = d[ x ][ k ];if( ans != -1 ) return ans;ans = 0;for( int i = 0 ; i <= k ; i++ ) ans = max( ans , dp( x - 1 , k - i ) + w[ x ][ i ] );return ans;}int main() {freopen( "test.in" , "r" , stdin );cin >> n >> m >> T;Rep( i , n ) {sum[ i ][ 0 ] = 0; Rep( j , m ) {char c = getchar();while( ! isdigit( c ) ) c = getchar();sum[ i ][ j ] += sum[ i ][ j - 1 ] + c - '0'; }}init();clr( d , -1 );memcpy( d[ 0 ] , w[ 0 ] , sizeof d[ 0 ] );cout << dp( n , T ) << "\n";return 0;}

---------------------------------------------------------------------------------------------

1296: [SCOI]粉刷匠

Time Limit:10 SecMemory Limit:162 MB

Submit:1056Solved:620

[Submit][Status][Discuss]

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 。

Source

Day2