BZOJ-3256: 基因序列相似性问题(KMP+DP)

作者: AmadeusChan | 来源:发表于2018-10-17 12:27 被阅读1次

    题目:http://www.lydsy.com/JudgeOnline/problem.php?id=3256

    裸裸的最长公共子序列问题,f( i , j , k )表示X匹配到i,Y匹配到j,P匹配到k的最长公共子序列,然后k用KMP维护就可以了。

    代码:

    #include <cstdio>
    
    #include <algorithm>
    
    #include <cstring>
    
     
    
    using namespace std ;
    
     
    
    #define update( i , j , k , f ) dp[ i ][ j ][ k ] = max( dp[ i ][ j ][ k ] , f )
    
    #define MAXN 210
    
     
    
    char s1[ MAXN ] , s2[ MAXN ] , s3[ MAXN ] ;
    
    int dp[ MAXN ][ MAXN ][ MAXN ] , n , m , p , pre[ MAXN ] ;
    
     
    
    int main(  ) {
    
        scanf( "%d%d%d" , &n , &m , &p ) ;
    
        scanf( "%s%s%s" , s1 + 1 , s2 + 1 , s3 + 1 ) ;
    
        memset( dp , 0 , sizeof( dp ) ) ;
    
        pre[ 1 ] = 0 ;
    
        for ( int i = 1 , j = 0 ; i ++ < p ; ) {
    
            for ( ; j && s3[ j + 1 ] != s3[ i ] ; j = pre[ j ] ) ;
    
            if ( s3[ j + 1 ] == s3[ i ] ) ++ j ;
    
            pre[ i ] = j ;
    
        }
    
        dp[ 0 ][ 0 ][ 0 ] = 1 ;
    
        for ( int i = 0 ; i <= n ; ++ i ) {
    
            for ( int j = 0 ; j <= m ; ++ j ) {
    
                for ( int k = 0 ; k < p ; ++ k ) {
    
                    if ( dp[ i ][ j ][ k ] ) {
    
                        if ( i < n && j < m && s1[ i + 1 ] == s2[ j + 1 ] )  {
    
                            int h = k ;
    
                            for ( ; h && s3[ h + 1 ] != s1[ i + 1 ] ; h = pre[ h ] ) ;
    
                            if ( s3[ h + 1 ] == s1[ i + 1 ] ) ++ h ;
    
                            if ( h < p ) update( i + 1 , j + 1 , h , dp[ i ][ j ][ k ] + 1 ) ;
    
                        }
    
                            if ( i < n ) update( i + 1 , j , k , dp[ i ][ j ][ k ] ) ;
    
                            if ( j < m ) update( i , j + 1 , k , dp[ i ][ j ][ k ] ) ;
    
                    }
    
                }
    
            }
    
        }
    
        int ans = 0 ;
    
        for ( int i = 0 ; i < p ; ++ i ) ans = max( ans , dp[ n ][ m ][ i ] ) ;
    
        printf( "%d\n" , ans - 1 ) ;
    
        return 0 ;
    
    }
    

    相关文章

      网友评论

        本文标题:BZOJ-3256: 基因序列相似性问题(KMP+DP)

        本文链接:https://www.haomeiwen.com/subject/gqnlzftx.html