# CFR 219 C. Color Stripe ( DP, Restoration )

Problem - 219C - Codeforces

dp[ i ][ j ] : 使前 i 個字母合法，最後一個字母為 'A' + j，此時的最少修改數。
dp[ i ][ j ] = min{ min{ dp[ i - 1 ][ k ] | k ≠ j }, dp[ i - 1 ][ j ] + 1 }

```int N, K;
string seq;

void init(){
cin >> N >> K;
cin >> seq;
}

vvi dp;
vvi pre;

void preprocess(){
dp = vvi( N + 1, vi( K, INF ) );
pre = vvi( N + 1, vi( K, -1 ) );
for( int i = 0; i < K; ++i )
dp[ 0 ][ i ] = 0;
for( int i = 0; i < N; ++i )
for( int j = 0; j < K; ++j )
if( dp[ i ][ j ] < INF )
for( int k = 0; k < K; ++k )
if( j != k )
if( upmin( dp[ i + 1 ][ k ], dp[ i ][ j ] + ( seq[ i ] != 'A' + k ) ) )
pre[ i + 1 ][ k ] = j;
}

void solve(){
int ans = INF;
for( int i = 0; i < K; ++i )
upmin( ans, dp[ N ][ i ] );
cout << ans << endl;
for( int i = 0; i < K; ++i )
if( ans == dp[ N ][ i ] ){
stack< char > show;
for( int u = i, n = N; ~pre[ n ][ u ]; u = pre[ n-- ][ u ] )
show.push( ( char )( 'A' + u ) );
for( ; not show.empty(); show.pop() )
cout << show.top();
cout << endl;
return;
}
}
```