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

const int Table[5][5] = { 5, -1, -2, -1, -3,
            -1, 5, -3, -2, -4,
            -2, -3, 5, -2, -2,
            -1, -2, -2, 5, -1,
            -3, -4, -2, -1, 0

} ;

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 巫 阅读(114) 评论(0)  编辑 收藏 引用 所属分类: DP

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