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