1080

#include

#include

#include

#include

#include

#include

#include

#include

#include

using namespace std;

#define MAX 102

int a[2][MAX];

int d[MAX][MAX];

// A C G T B 其中B表示空格

int  hash[26];

int  score[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  

};

int main()

{

#ifdef LOCAL

freopen("data.in","r",stdin);

freopen("data.out","w",stdout);

#endif

    hash['A'-'A']=0;

    hash['C'-'A']=1;

    hash['G'-'A']=2;

hash['T'-'A']=3;

int n,i,j,k,m,h;

char tmp;

cin>>n;

for(i=0;i

{

memset(a,0,sizeof(a));

memset(d,0,sizeof(d));

//分开输入为了保留长度信息

cin>>k;

for(j=1;j<=k;j++)

{

cin>>tmp;

a[0][j]=hash[tmp-'A'];

}

cin>>m;

for(j=1;j<=m;j++)

{

cin>>tmp;

a[1][j]=hash[tmp-'A'];

}

//初始化

d[0][0] =0;

for(j=1;j<=m;j++)  //a[1]

d[j][0] =  d[j-1][0] + score[a[1][j]][4];

for(h=1;h<=k;h++)  //a[0]

d[0][h] = d[0][h-1] + score[4][a[0][h]];

for(j=1;j<=m;j++)  //a[1]

for(h=1;h<=k;h++)  //a[0]

d[j][h] = max(max(d[j-1][h]+score[ a[1][j] ][4],d[j][h-1]+score[4][a[0][h]]) , d[j-1][h-1]+score[a[1][j]][a[0][h]]);

cout<

}

return 0;

}

阅读(826) | 评论(0) | 转发(0) |

0

上一篇：判断链表是否有环及环的位置问题

下一篇：1159