注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

GreenCloudS

 
 
 

日志

 
 

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

2014-02-05 18:23:00|  分类: oi,bzoj,dp,kmp |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

题目: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 ;

  • }



  评论这张
 
阅读(5)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018