2165: 宝典2第十一章确定基因功能

【问题描述】确定基因功能（gene.cpp/c/pas) taejon 2001

　　我们都知道人体基因是由一个序列组成，包含4个核苷酸，我们以A、C、G、T表示。魔法世界的生物学家需要确定人体基因并确定其功能，以开发新的药品抵抗天顶星人的基因武器。

　　人体基因的确定由计算机辅导并通过一系列生物实验，一旦基因被确定，下一步的工作即是确定其功能。

    一种方法是：通过数据库查询新的基因，这个数据存储了许多基因序列及其功能描述，当使用数据库查找时，数据库会返回相类似的基因。而生物学家假设序列相似代表功能的相似，所以，新基因可能会有的功能与相似基因的功能一样。当然，这需要一系列的实验确定。

你的职责是编制一个程序以比较两个相似的基因，如果你的程序有效，你的程序可能会作为数据库搜索功能的一部分。

　　例如：两个基因AGTGATG 和GTTAG，有多少相似度呢？
    我们使用插入法：例如，插入一个空档在AGTGATG中间，使之变为AGTGAT–G，再插入三个空档在GTTAG中间，使之变为–GT– –TAG，现在这两个基因长度相等。如下：

　　AGTG AT–G，

　　– GT – –TAG

　　我们可以看到，两个基因有四处相似，即：G都在第2位，T都在第3位，T都在第6位，G都在第8位。

表是任何两个核苷酸相对应时的数字矩阵，例如A与A对应的分数为5，A与C对应的分数为－1，但要注意绝对不允许空档与空档匹配情况的出现。

则这两个基因根据该表格算出的分数为：(－3)+5+5+(－2)+(－3)+5+(－3)+5=9。

　　但实际上，如果我们将这两个基因按如下方式插入空档，即：

　　AGTGATG

　　– GTTA –G

　　这种方式的分数为 (－3)+5+5+(－2)+5+(－1)+5=14。所以，这种插入方式要优于前面的插入方式，而实际上，这种插入方式的得分也是最高的，所以，这两个基因的相似程度应该为14。

　　【输入格式】

　　第一行为T值，代表测试的样例数，接下来每个测试样例包括两行，每行包括一个基因长度数和该基因序列，每个基因的序列长度最小为1，最大不超过100。

　　【输出格式】

　　每行包括一个数字，即每个样例的最大相似度。

　　【样例输入】

　　2

　　7 AGTGATG

　　5 GTTAG

　　7 AGCTATT

　　9 AGCTTTAAA

　　【样例输出】

　　14

　　21