动态规划(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,
                  
-15-3-2-4,
                  
-2-35-2-2,
                  
-1-2-25-1,
                  
-3-4-2-10,
                }
;

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;
}