大概作了一周，终于A了
类似于求最长公共子序列，稍有变形
当前序列 ch1 中字符为 a，序列 ch2 中字符为 b
则有 3 种配对方式：
1. a 与 b
2. a 与 -
3. - 与 b
动态转移方程：
dp[i][j] = max(dp[i - 1][j - 1] + g(ch1[i],ch2[j]) , dp[i - 1][j] + g(ch1[i],‘-') , dp[i][j-1] + g('-',ch2[j]))
代码如下：
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int dp[][];
int g(char a,char b)
{
if( a == b ) return ;
if(a == 'A' && b == 'C' || b == 'A' && a == 'C') return -;
if(a == 'A' && b == 'G' || b == 'A' && a == 'G') return -;
if(a == 'A' && b == 'T' || b == 'A' && a == 'T') return -;
if(a == 'C' && b == 'G' || b == 'C' && a == 'G') return -;
if(a == 'C' && b == 'T' || b == 'C' && a == 'T') return -;
if(a == 'G' && b == 'T' || b == 'G' && a == 'T') return -;
if(a == 'A' && b == '-' || b == 'A' && a == '-') return -;
if(a == 'C' && b == '-' || b == 'C' && a == '-') return -;
if(a == 'G' && b == '-' || b == 'G' && a == '-') return -;
if(a == 'T' && b == '-' || b == 'T' && a == '-') return -;
}
int main()
{
char ch1[],ch2[];
int t,s1,s2;
scanf("%d",&t);
while(t--)
{
memset(dp,,sizeof(dp));
scanf("%d %s",&s1,ch1 + );
scanf("%d %s",&s2,ch2 + );
for(int i = ; i <= s1 ; i ++)
dp[i][] = dp[i - ][] + g('-',ch1[i]);
for(int i = ; i <= s2 ; i ++)
dp[][i] = dp[][i - ] + g(ch2[i],'-');
for(int i = ; i <= s1 ; i ++)
for(int j = ; j <=s2 ; j ++)
dp[i][j] = max(dp[i-][j-] + g(ch1[i],ch2[j]),
max(dp[i-][j] + g(ch1[i],'-'),dp[i][j - ] + g('-',ch2[j])));
printf("%d\n",dp[s1][s2]);
}
return ;
}