hdu1080

#include<iostream>
using namespace std;

char s1[105],s2[105];
int val[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,-1000000}};

int dp[105][105]; //dp[i][j]表示字符串i和j的最长公共子序列
int n,m;

int max(int a,int b)
{
return a>b?a:b;
}

int id(char c)
{
switch(c)
{
case 'A':
return 0;
break;

case 'C':
return 1;
break;

case 'G':
return 2;
break;

case 'T':
return 3;
break;
}
}

int fun()
{
int i,j;

memset(dp,0,sizeof(dp));
for(i=1;i<=n;i++)
dp[i][0]=dp[i-1][0]+val[id(s1[i-1])][4];
for(j=1;j<=m;j++)
dp[0][j]=dp[0][j-1]+val[id(s2[j-1])][4];

for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
dp[i][j]=max(dp[i-1][j]+val[id(s1[i-1])][4],
max(dp[i][j-1]+val[id(s2[j-1])][4],dp[i-1][j-1]+val[id(s1[i-1])][id(s2[j-1])]));
return dp[n][m];
}

int main()
{
int T;

cin>>T;
while(T--)
{
cin>>n>>s1>>m>>s2;
cout<<fun()<<endl;
}
return 0;
}

巴特西

hdu1080

最新文章

热门文章