# CFR 225 C. Barcode ( DP )

Problem - 225C - Codeforces

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