题目翻译
众所周知，人类基因可以被视为一个序列，由四个核苷酸组成，它们简单地由四个字母A、C、G和T表示。生物学家一直对识别人类基因和确定其功能感兴趣，因为这些基因可以用于诊断人类疾病和为其设计新药。
人类基因可以通过一系列耗时的生物学实验来识别，通常需要计算机程序的帮助。一旦获得了基因序列，下一步的工作就是确定它的功能。生物学家在确定刚刚确定的新基因序列的功能时使用的一种方法是搜索带有新基因的数据库作为查询。要搜索的数据库存储了许多基因序列及其功能——许多研究人员一直在向数据库提交他们的基因和功能，数据库可以通过互联网*访问。
数据库搜索将返回数据库中与查询基因相似的基因序列列表。生物学家认为序列相似性通常意味着功能相似性。因此，新基因的功能可能是列表中的基因所具有的功能之一。为了准确地确定哪一个是正确的，还需要一系列的生物学实验。
你的工作是制作一个程序来比较两个基因并确定它们的相似性，如下所述。如果您能提供一个高效的程序，您的程序可以用作数据库搜索的一部分。给定两个基因AGTGATG和GTTAG，它们有多相似？相似性度量方法之一两个基因的结合称为对齐。在路线中，如有必要，将在路线的适当位置插入空间这些基因使它们同样长，并根据评分矩阵对结果基因进行评分。
例如，将一个空格插入AGTGATG以生成AGTGAT-G，将三个空格插入GTTAG以生成–GT--TAG。空格由减号（-）表示。这两个基因现在具有相同的功能长这两个字符串是对齐的：
AGTGAT-G
-GT--TAG
在这个排列中，有四个匹配，即G在第二个位置，T在第三个位置，T在第六个位置，G在第八个位置。每对对齐字符根据以下评分矩阵分配一个分数。
表示不允许空间匹配。以上排列的得分为（-3）+5+5+（-2）+ (-3）+5+（-3）+5=9。
当然，许多其他路线也是可能的。下面显示了一个（在不同位置插入不同数量的空格）：
AGTGATG
-GTTA-G
此对齐方式的得分为（-3）+5+5+（-2）+5+（-1）+5=14。所以，这个比前一个好。事实上，这一条是最优的，因为没有其他路线可以有更高的分数。因此，说这两个基因的相似性为14。
输入
输入由T个测试用例组成。测试用例数）（T在输入文件的第一行中给出。每个测试用例由两行组成：每行包含一个整数，即基因长度，后跟一个基因序列。每个基因序列的长度至少为一个，且不超过100。
输出
输出应该打印每个测试用例的相似性，每行一个。
样例
输入
2 7 AGTGATG 5 GTTAG 7 AGCTATT 9 AGCTTTAAA
输出
14
21
解题思路
把表对应到二维数组里面，之后读入的时候可以把行列对应的字母改成数字。
对应情况严格来说就三种，s1[i]对应‘-’，‘-’对应s2[i]，s1[i]对应s2[i]。
类似于动态规划中的，找最长公共子序列，那么这道题的动态转移方程也很好推了
代码示例
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
int t;
int len_1,len_2;
int dp[1100][1100];
string s_1,s_2;
int match[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,'*'
};
int get_num(char x){
if(x=='A') return 0;
if(x=='C') return 1;
if(x=='G') return 2;
if(x=='T') return 3;
if(x=='-') return 4;
}
int main(){
cin>>t;
while(t--){
cin>>len_1;
cin>>s_1;
cin>>len_2;
cin>>s_2;
memset(dp,0,sizeof(dp));
for(int i=1;i<=len_1;i++){
dp[i][0]=dp[i-1][0]+match[get_num(s_1[i-1])][get_num('-')];
}
for(int i=1;i<=len_2;i++){
dp[0][i]=dp[0][i-1]+match[get_num('-')][get_num(s_2[i-1])];
}
for(int i=1;i<=len_1;i++){
for(int j=1;j<=len_2;j++){
dp[i][j]=max(dp[i-1][j]+match[get_num(s_1[i-1])][get_num('-')],max(dp[i][j-1]+match[get_num('-')][get_num(s_2[j-1])],dp[i-1][j-1]+match[get_num(s_1[i-1])][get_num(s_2[j-1])]));
}
}
cout<<dp[len_1][len_2]<<endl;
}
}