#HXOJ3472. 最长公共子序列题四：基因相似度
题目描述
题目描述
人类基因由字母 A、C、G、T 组成。比较两条基因时，可以在任意位置插入空位 -，使两条序列等长，但同一列不能同时为空位。每一列的得分由下表确定，所有列得分之和称为相似度。请计算能够得到的最大相似度。
| A | C | G | T | - | |
|---|---|---|---|---|---|
| A | 5 | -1 | -2 | -1 | -3 |
| C | -1 | 5 | -3 | -2 | -4 |
| G | -2 | -3 | 5 | -2 | |
| T | -1 | -2 | -2 | 5 | -1 |
| - | -3 | -4 | -1 |
输入格式
第一行输入第一条基因的长度 和字符串 。
第二行输入第二条基因的长度 和字符串 。
输出格式
输出一个整数，表示最大相似度。
数据范围与约定
；基因串仅包含 A、C、G、T。
可见测试数据
输入数据 1
7 AGTGATG
5 GTTAG
输出数据 1
14
输入数据 2
7 AGCTATT
9 AGCTTTAAA
输出数据 2
21
输入数据 3
5 ATCAA
3 TCA
输出数据 3
9