题目地址：http://acm.hdu.edu.cn/showproblem.php?pid=1080
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
const int maxn=100+5;
const int INF=0x3f3f3f3f;
#define max3(a,b,c) max(a,max(b,c))
char s1[maxn],s2[maxn];
int d[maxn][maxn],len1,len2;
//d[i][j]表示s1前i个和s2前j个匹配的最大值
char str[]="ACGT-";
int score[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 inline Value(char a,char b){int p1=find(str,str+5,a)-str;int p2=find(str,str+5,b)-str;return score[p1][p2];
}
int solve()
{memset(d,-INF,sizeof(d));d[0][0]=0;for(int i=1;i<=len1;i++){d[i][0]=d[i-1][0]+Value(s1[i],'-');d[0][i]=d[0][i-1]+Value(s2[i],'-');}for(int i=1;i<=len1;i++)for(int j=1;j<=len2;j++)d[i][j]=max3(d[i-1][j-1]+Value(s1[i],s2[j]),d[i-1][j]+Value(s1[i],'-'),d[i][j-1]+Value(s2[j],'-'));//s1[i]和s2[j] 匹配 s1[i]和'-'匹配 s2[j]和'-'匹配return d[len1][len2];
}
int main(int argc, char const *argv[])
{int T; cin>>T;while(T--){scanf("%d %s",&len1,s1+1);scanf("%d %s",&len2,s2+1);cout<<solve()<<endl;}return 0;
}