UVa1207 - AGTC (LCS)

題目大意:

有 a , b 兩個字串求他們的 LCS(最長公共子序列) 最短修改數?

分析:

LCS 與 LCS-less modify

透過此圖可以了解 DP 原理

LCS 遞迴公式:

• LCS(x, y) =
  • max( LCS( x-1, y ), LCS( x , y-1 ) ) , when str[x] != str[y]
  • LCS( x-1 , y-1 ) + e1 , when str[x] == sty[y]

LCS-less modify(LCS-lm) 遞迴公式:

• LCS-lm( x, y ) =
  • min( LCS-lm( x , y ), LCS-lm( x , y) , LCS-lm( x-1 , y-1) ) +1 , when str[x] != str[y]
  • LCS-lm( x -1 , y -1 ) +1 , when str[x] == str[y]

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


struct LCS{
    int step , max_len ;
}Dp[5000][5000];


int main()
{
#ifdef LOCAL
    freopen("in1.txt" , "r" , stdin );
#endif // LOCAL
    int intX , intY , Min_step , Max_len ;
    string strX , strY ;
    while(cin >> intX >> strX >> intY >> strY ){
        //init
        for(int i = 0 ; i <= intY ; i++){
            Dp[0][i].max_len = 0 ;
            Dp[0][i].step = i ;
        }
        for(int i = 0 ; i <= intX ; i++){
            Dp[i][0].max_len = 0 ;
            Dp[i][0].step = i ;
        }
        Max_len = 0 ;
        Min_step = 0 ;

        //lcs
        for(int i = 1 ; i <= intX ; i++){
            for(int j = 1 ; j <= intY ; j++){
                if(strX[i-1] == strY[j-1]){
                    Dp[i][j].max_len = Dp[i-1][j-1].max_len +1 ;
                    Dp[i][j].step = Dp[i-1][j-1].step ;

                    //debug
                    //cout << strX[i-1] << ' ' << strY[j-1] << ' ' << Dp[i][j].max_len << '\n' ;
                    //cout << strX[i-1] << ' ' << strY[j-1] << ' ' << Dp[i][j].step << '\n' ;
                }
                else{
                    Dp[i][j].max_len = max(Dp[i-1][j].max_len , Dp[i][j-1].max_len ) ;
                    Dp[i][j].step = min( min(Dp[i-1][j-1].step , Dp[i][j-1].step ) , Dp[i-1][j].step ) +1 ;
                }
            }
        }
        cout << Dp[intX][intY].step << '\n' ;
    }
    return 0;
}