0w1

CFR 225 C. Barcode ( DP )

Problem - 225C - Codeforces
題意:
給 N * M 的圖,每個格子表示黑白。求修改顏色至合法的最少步數。每一直列必須是同一顏色,且同一顏色不能連續低於 X 或超過 Y 列。
解法:
預處理每一列變成某一顏色的 cost。
cost[ i ][ j ] : 第 j 列的所有顏色變白色的最少步數。
dp[ i ][ j ][ k ] : 考慮前 M 列,最後一種顏色以持續 j 列,最後一種顏色是白色,此時修改至合法的最小步數。
dp[ i ][ j ][ k ] = min{ ( dp[ i - 1 ][ j - 1 ][ k ] + cost[ k ][ i - 1 ], if j ≤ Y ), min{ dp[ i - 1 ][ t ][ k ^ 1 ] + cost[ k ^ 1 ][ i - 1 ] | X ≤ t ≤ Y }

int N, M, L, R;
vs G;

void init(){
    cin >> N >> M >> L >> R;
    G = vs( N );
    for( int i = 0; i < N; ++i )
        cin >> G[ i ];
}

vvi cost;
vvvi dp;

void preprocess(){
    cost = vvi( 2, vi( M ) );
    for( int i = 0; i < M; ++i )
        for( int j = 0; j < N; ++j )
            cost[ 0 ][ i ] += G[ j ][ i ] == '#',
            cost[ 1 ][ i ] += G[ j ][ i ] == '.';
    dp = vvvi( M + 1, vvi( R + 1, vi( 2, INF ) ) );
    dp[ 0 ][ 0 ][ 0 ] = dp[ 0 ][ 0 ][ 1 ] = 0;
    for( int i = 0; i < M; ++i )
        for( int j = 0; j <= R; ++j )
            for( int k = 0; k < 2; ++k ){
                if( L <= j )
                    upmin( dp[ i + 1 ][ 1 ][ k ^ 1 ], dp[ i ][ j ][ k ] + cost[ k ^ 1 ][ i ] );
                if( j + 1 <= R )
                    upmin( dp[ i + 1 ][ j + 1 ][ k ], dp[ i ][ j ][ k ] + cost[ k ][ i ] );
            }
}

void solve(){
    int ans = INF;
    for( int i = L; i <= R; ++i )
        for( int k = 0; k < 2; ++k )
            upmin( ans, dp[ M ][ i ][ k ] );
    cout << ans << endl;
}