#include <stdio.h>
#define MAX 150
int score[MAX][MAX], lena, lenb;
char a[MAX], b[MAX];
int dict[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, -127
};
int solve(void)
{
int i, j;
score[0][0] = 0;
for(i = 1; i <= lena; i++){
score[i][0] = score[i-1][0] + dict[a[i-1]-'0'][4];
}
for(j = 1; j <= lenb; j++){
score[0][j] = score[0][j-1] + dict[4][b[j-1]-'0'];
}
for(i = 1; i <= lena; i++){
for(j = 1; j <= lenb; j++){
score[i][j] = score[i-1][j-1] + dict[a[i-1]-'0'][b[j-1]-'0'];
if(score[i][j] < score[i-1][j] + dict[a[i-1]-'0'][4]){
score[i][j] = score[i-1][j] + dict[a[i-1]-'0'][4];
}
if(score[i][j] < score[i][j-1] + dict[4][b[j-1]-'0']){
score[i][j] = score[i][j-1] + dict[4][b[j-1]-'0'];
}
}
}
return score[lena][lenb];
}
int main(int argc, char **arv)
{
int i, cases;
scanf("%d", &cases);
getchar();
while(cases--){
scanf("%d ", &lena);
for(i = 0; i < lena; i++){
scanf("%c", &a[i]);
switch(a[i]){
case 'A':
a[i] = '0';
break;
case 'C':
a[i] = '1';
break;
case 'G':
a[i] = '2';
break;
case 'T':
a[i] = '3';
break;
}
}
getchar();
scanf("%d ", &lenb);
for(i = 0; i < lenb; i++){
scanf("%c", &b[i]);
switch(b[i]){
case 'A':
b[i] = '0';
break;
case 'C':
b[i] = '1';
break;
case 'G':
b[i] = '2';
break;
case 'T':
b[i] = '3';
break;
}
}
getchar();
printf("%d\n", solve());
}
return 0;
}
|