动态规划(DP)，地址：http://acm.pku.edu.cn/JudgeOnline/problem?id=1080
#include <stdio.h>

char tab[5] = {'A', 'C', 'G', 'T', '-'};

int list[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 str1[105];
int str2[105];

int dp[105][105];

int find(char ch)
{
    
    int i;
    for (i=0; i<5; i++)
    {
        if (tab[i]==ch)
        {
            break;
        }
    }
    return i;
}

int max(int a, int b, int c)
{

    int m = a;
    if (b>m)
    {
        m = b;
    }
    if (c>m)
    {
        m = c;
    }
    return m;
}

int lcs(int s1[], int len1, int s2[], int len2)
{

    int i, j;
    for (i=0; i<=len1; i++)
    {
        for (j=0; j<=len2; j++)
        {
            if (i==0 && j==0)
            {
                dp[i][j] = 0;
            }
            else if (i==0 && j!=0)
            {
                dp[i][j] = dp[i][j-1] + list[4][s2[j-1]];
            }
            else if (i!=0 && j==0)
            {
                dp[i][j] = dp[i-1][j] + list[s1[i-1]][4];
            }
            else
            {
                dp[i][j] = max(dp[i-1][j-1]+list[s1[i-1]][s2[j-1]], dp[i][j-1]+list[4][s2[j-1]], dp[i-1][j]+list[s1[i-1]][4]);
            }
        }
    }
    return dp[i-1][j-1];
}

int main()
{

    int t, n1, n2;
    int i;
    char temp[105];
    while (scanf("%d", &t) != EOF)
    {
        while (t--)
        {
            scanf("%d%s", &n1, &temp);
            for (i=0; i<n1; i++)
            {
                str1[i] = find(temp[i]);
            }
            scanf("%d%s", &n2, &temp);
            for (i=0; i<n2; i++)
            {
                str2[i] = find(temp[i]);
            }
            printf("%d\n", lcs(str1, n1, str2, n2));
        }
    }
    return 0;
}