学步园

#include <iostream>
#include <cstdio>
using namespace std;

inline int max( int a, int b, int c ){
	int maxi = a;
	maxi = ( maxi > b ? maxi : b );
	maxi = ( maxi > c ? maxi : c );
	return maxi;
}

int main(){
	int score[6][6] = {
		0, 0, 0, 0, 0, 0,
		0, 5, -1, -2, -1, -3,
		0, -1, 5, -3, -2, -4,
		0, -2, -3, 5, -2, -2,
		0, -1, -2, -2, 5, -1,
		0, -3, -4, -2, -1, -100000
	};
	int t, n1, n2;
	char c1[101], c2[101];
	int a1[101], a2[101], dp[101][101];

	cin >> t;
	while( t-- ){
		cin >> n1;
		scanf( "%s", c1 + 1 );
		for( int i = 1; i <= n1; i++ ){
			if( c1[i] == 'A' ) a1[i] = 1;
			else if( c1[i] == 'C' ) a1[i] = 2;
			else if( c1[i] == 'G' ) a1[i] = 3;
			else a1[i] = 4;
		}
		cin >> n2;
		scanf( "%s", c2 + 1 );
		for( int i = 1; i <= n2; i++ ){
			if( c2[i] == 'A' ) a2[i] = 1;
			else if( c2[i] == 'C' ) a2[i] = 2;
			else if( c2[i] == 'G' ) a2[i] = 3;
			else a2[i] = 4;
		}
		dp[0][0] = 0;
		for( int i = 1; i <= n1; i++ ){
			dp[i][0] = dp[i-1][0] + score[a1[i]][5];
		}
		for( int i = 1; i <= n2; i++ ){
			dp[0][i] = dp[0][i-1] + score[5][a2[i]];
		}
		for( int i = 1; i <= n1; i++ ){
			for( int j = 1; j <= n2; j++ ){
				dp[i][j] = max( dp[i-1][j-1] + score[a1[i]][a2[j]], dp[i][j-1] + score[5][a2[j]], dp[i-1][j] + score[a1[i]][5] );
			}
		}
		cout << dp[n1][n2] << endl;
	}
	return 0;
}