题意读了半年，唉，给你两串字符，然后长度不同，你能够用‘-’把它们补成同样长度，补在哪里取决于得分，它会给你一个得分表，问你最大得分

跟LCS非常像的DP数组 dp[i][j]表示第一个字符串取第i个元素第二个字符串取第三个元素，然后再预处理一个得分表加上就可以

得分表：

score['A']['A'] = score['C']['C'] = score['G']['G'] = score['T']['T'] = 5;

	score['A']['C'] = score['C']['A'] = -1;

	score['A']['G'] = score['G']['A'] = -2;

	score['A']['T'] = score['T']['A'] = -1;

	score['A']['-'] = score['-']['A'] = -3;

	score['C']['G'] = score['G']['C'] = -3;

	score['C']['T'] = score['T']['C'] = -2;

	score['C']['-'] = score['-']['C'] = -4;

	score['G']['T'] = score['T']['G'] = -2;

	score['G']['-'] = score['-']['G'] = -2;

	score['T']['-'] = score['-']['T'] = -1;

	score['-']['-'] = -inf;

那么DP方程就好推了：

dp[i][j] = ：

dp[i-1][j] + score[s1[i-1]]['-']或者

dp[i][j-1] + score['-'][s2[j-1]]或者

dp[i-1][j-1] + score[s1[i-1]][s2[j-1]]或者

这三者之中取最大的

然后就是边界问题我给忘记了

不够细心，若单单是i==0或者j==0，边界问题就出现了，边界不可能为0的，所以还得处理一下边界

#include<iostream>

#include<cstdio>

#include<list>

#include<algorithm>

#include<cstring>

#include<string>

#include<queue>

#include<stack>

#include<map>

#include<vector>

#include<cmath>

#include<memory.h>

#include<set>

#include<cctype>

#define ll long long

#define LL __int64

#define eps 1e-8

#define inf 0xfffffff

//const LL INF = 1LL<<61;

using namespace std;

//vector<pair<int,int> > G;

//typedef pair<int,int > P;

//vector<pair<int,int> > ::iterator iter;

//

//map<ll,int >mp;

//map<ll,int >::iterator p;

const int N = 1000 + 5;

int dp[N][N];

int score[200][200];

void init() {

	score['A']['A'] = score['C']['C'] = score['G']['G'] = score['T']['T'] = 5;

	score['A']['C'] = score['C']['A'] = -1;

	score['A']['G'] = score['G']['A'] = -2;

	score['A']['T'] = score['T']['A'] = -1;

	score['A']['-'] = score['-']['A'] = -3;

	score['C']['G'] = score['G']['C'] = -3;

	score['C']['T'] = score['T']['C'] = -2;

	score['C']['-'] = score['-']['C'] = -4;

	score['G']['T'] = score['T']['G'] = -2;

	score['G']['-'] = score['-']['G'] = -2;

	score['T']['-'] = score['-']['T'] = -1;

	score['-']['-'] = -inf;

}

int main () {

	init();

	int t;

	char s1[N];

	char s2[N];

	scanf("%d",&t);

	while(t--) {

		int n,m;

		memset(dp,0,sizeof(dp));

		scanf("%d %s",&n,s1);

		scanf("%d %s",&m,s2);

		for(int i=1;i<=n;i++)

			dp[i][0] = dp[i-1][0] + score[s1[i-1]]['-'];//边界处理

		for(int j=1;j<=m;j++)

			dp[0][j] = dp[0][j-1] + score['-'][s2[j-1]];//边界处理

		for(int i=1;i<=n;i++) {

			for(int j=1;j<=m;j++) {

				int t1 = dp[i-1][j] + score[s1[i-1]]['-'];

				int t2 = dp[i][j-1] + score['-'][s2[j-1]];

				int t3 = dp[i-1][j-1] + score[s1[i-1]][s2[j-1]];

				int maxn = max(t1,t2);

				dp[i][j] = max(maxn,t3);

			}

		}

		printf("%d\n",dp[n][m]);

	}

	return 0;

}