台北市104 學年度資訊學科能力競賽 pD. Guess ( DP )

dp[ i ][ j ] : 考慮完 B 字串的第 i 個字元，其尾端有 j 個字元是 A 字串的前綴，且B不含A，此時修改次數的最小值。
修改最後一個字元之後，尋找其最長的後綴使 A 的前綴與之相同。這部分用預處理。

#include <bits/stdc++.h>
using namespace std;

typedef vector< int > vi;
typedef vector< vi > vvi;

const int INF = 0x3f3f3f3f;

template< class T1, class T2 >
int upmin( T1 &x, T2 v ){
    if( x > v ){
        x = v;
        return 1;
    }
    return 0;
}

template< class T1, class T2 >
int upmax( T1 &x, T2 v ){
    if( x < v ){
        x = v;
        return 1;
    }
    return 0;
}

string A, B;

void init(){
    cin >> A >> B;
}

void solve(){
    vvi nxt( A.size(), vi( 2 ) );
    for( int i = 0; i < A.size(); ++i ){
        for( int k = 0; k < 2; ++k ){
            string x = A.substr( 0, i + 1 );
            string y = x.substr( 0, x.size() - 1 ) + ( char )( ( x.back() - 'A' + k ) % 2 + 'A' );
            for( int j = ( int )x.size(); j >= 0; --j ){
                string s = x.substr( 0, j );
                string t = y.substr( y.size() - j );
                if( s == t ){
                    nxt[ i ][ k ] = j;
                    break;
                }
            }
        }
    }

    vvi dp( B.size() + 1, vi( A.size() + 1, INF ) );
    dp[ 0 ][ 0 ] = 0;
    for( int i = 0; i < B.size(); ++i )
        for( int j = 0; j < A.size(); ++j ){
            if( B[ i ] == A[ j ] ){ // assert( nxt[ j ][ 0 ] == j + 1 );
                upmin( dp[ i + 1 ][ nxt[ j ][ 0 ] ], dp[ i ][ j ] );
                upmin( dp[ i + 1 ][ j ], dp[ i ][ j ] + 1 );
            } else{
                upmin( dp[ i + 1 ][ nxt[ j ][ 1 ] ], dp[ i ][ j ] );
                upmin( dp[ i + 1 ][ j ], dp[ i ][ j ] + 1 );
            }
        }

    int ans = INF;
    for( int i = 0; i < A.size(); ++i )
        upmin( ans, dp[ B.size() ][ i ] );
    cout << ans << endl;
}

signed main(){
    ios::sync_with_stdio( 0 );
    init();
    solve();
    return 0;
}