gzwzm06

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  1 随笔 :: 52 文章 :: 17 评论 :: 0 Trackbacks
#include <stdio.h>

const int Table[5][5= 5-1-2-1-3,
            
-15-3-2-4,
            
-2-35-2-2,
            
-1-2-25-1,
            
-3-4-2-10

}
 ;

const int MAXN = 102 ;

int Ctoi( char &c )
{
    
switch( c )
    
{
    
case 'A':
        
return 0 ;
    
case 'C':
        
return 1 ;
    
case 'G':
        
return 2 ;
    
case 'T':
        
return 3 ;
    }

    
return -1 ;
}


int main()
{
    
int N , m , n , i , j , Ftmp[MAXN] , Stmp[MAXN] ;
    
int mem[MAXN][MAXN] ;
    
char str1[MAXN], str2[MAXN] ;
    scanf(
"%d"&N) ;

    
for ( i = 0 ; i < N ; ++i )
    
{
        scanf(
"%d %s"&m, &str1) ;
        scanf(
"%d %s"&n, &str2) ;

        
for ( j = 0 ; j < m ; ++j )
        
{
            Ftmp[j 
+ 1= Ctoi( str1[j] ) ;
        }

        
for ( j = 0 ; j < n ; ++j )
        
{
            Stmp[j 
+ 1= Ctoi( str2[j] ) ;
        }


        mem[
0][0= 0 ;

        
for ( j = 1 ; j <= m ; ++j )
        
{
            mem[j][
0= mem[j - 1][0]+ Table[4][Ftmp[j]] ;
        }

        
for ( j = 1 ; j <= n ; ++j )
        
{
            mem[
0][j] = mem[0][j - 1+ Table[4][Stmp[j]] ;
        }


        
int k ;

        
for ( j = 1 ; j <= m ; ++j )
            
for ( k = 1 ; k <= n ; ++k )
            
{
                mem[j][k] 
= mem[j - 1][k - 1+ Table[Ftmp[j]][Stmp[k]] ;
                
if ( mem[j][k] < mem[j - 1][k] + Table[Ftmp[j]][4] )
                    mem[j][k] 
= mem[j - 1][k] + Table[Ftmp[j]][4] ;
                
if ( mem[j][k] < mem[j][k - 1+ Table[4][Stmp[k]] )
                    mem[j][k] 
= mem[j][k - 1+ Table[4][Stmp[k]] ;
            }


        printf(
"%d\n", mem[m][n]) ;
    }

    
return 0 ;
}
posted on 2008-10-31 20:16 阅读(128) 评论(0)  编辑 收藏 引用 所属分类: DP

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理