#include<stdio.h>
#include <string.h>
char a[100],b[100],c[100];
int max;
int ctoi(char a)
{
    if(a=='A')
    return 0;
    if(a=='C')
    return 1;
    if(a=='G')
    return 2;
    if(a=='T')
    return 3;
    if(a=='-')
    return 4;
}
int fun2(char a,char b)
{   
    int arr[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}};
    return arr[ctoi(a)][ctoi(b)];
}



int fun(char *s,int n,int l)
{

    char s1[100];
    int i,j;
    int sum=0;
    if(l==0)
    {
        /* printf("%s\n",s); */
        for(i=0;i<strlen(a);i++)
        {
        sum+=fun2(a[i],s[i]);
        }
        if(sum>max)
        max=sum;
            
        return 0;
    }
    strcpy(s1,s);
    for(i=0;i<=n;i++)
    {
        strcpy(s1,s);
        for(j=n-1;j>=i;j--)
        s1[j+1]=s1[j];
        s1[i]='-';
        s1[n+1]='\0';
        fun(s1,n+1,l-1);
    }
}

int main()
{
int t,i,m,n,temp;
scanf("%d",&t);
for(i=0;i<t;i++)
{

    scanf("%d%s",&m,a);
    scanf("%d%s",&n,b);
    max=-3775;
    if(m<n)
    {
        strcpy(c,a);
        strcpy(a,b);
        strcpy(b,c);
        temp=m;
        m=n;
        n=temp;
    }
    fun(b,strlen(b),m-n);
    printf("%d\n",max);
}
}



    

评论