台北市104 學年度資訊學科能力競賽 pB. Party ( LCS )

把其中一個字串的0和1對調就是標準的 LCS。

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

typedef long long ll;
typedef vector< int > vi;
typedef vector< vi > vvi;
typedef pair< int, int > pii;

template< class T1, class T2 >
bool upmin( T1 &x, T2 v ){
    if( x > v ){
        x = v;
        return true;
    }
    return false;
}

template< class T1, class T2 >
bool upmax( T1 &x, T2 v ){
    if( x < v ){
        x = v;
        return true;
    }
    return false;
}

void solve(){
    int N, M; cin >> N >> M;
    vi A( N );
     for( int i = 0; i < N; ++i )
         cin >> A[ i ];
    vi B( M );
    for( int i = 0; i < M; ++i )
        cin >> B[ i ];
    vvi dp( N + 1, vi( M + 1 ) );
    for( int i = 0; i <= N; ++i)
        for( int j = 0; j <= M; ++j ){
            if( i + 1 <= N )
                upmax( dp[ i + 1 ][ j ], dp[ i ][ j ] );
            if( j + 1 <= M )
                upmax( dp[ i ][ j + 1 ], dp[ i ][ j ] );
            if( i < N and j < M and A[ i ] != B[ j ] )
                upmax( dp[ i + 1 ][ j + 1 ], dp[ i ][ j ] + 1 );
        }
    cout << dp[ N ][ M ] << endl;
}

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