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; }