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

int llen,rlen;
char lefts[101];
char rights[101];

int a[5][5];

int cost[100][100];


int get(char c){
	if(c=='A')return 0;
	else if(c=='C')return 1;
	else if(c=='G')return 2;
	else if(c=='T')return 3;
	else return 4;
}
int maxint(int a,int b,int c){
	if(a>b){
		if(a>c)return a;
		else return c;
	}else{
		if(b>c)return b;
		else return c;
	}
}

int cal(int m,int n){
	if(cost[m][n]!=0)return cost[m][n];
	if(m==0||n==0){
		return cost[m][n];
	}else{
		int max=-1000;
		int tmp1=a[get(lefts[m-1])][get(rights[n-1])]+cal(m-1,n-1);
		int tmp2=a[4][get(rights[n-1])]+cal(m,n-1);
		int tmp3=a[get(lefts[m-1])][4]+cal(m-1,n);
		max=maxint(tmp1,tmp2,tmp3);
		cost[m][n]=max;
		return max;
	}
}


void init(){
	for(int i=0;i<4;i++)
		a[i][i]=5;
	a[0][1]=a[1][0]=-1;a[0][2]=a[2][0]=-2;a[0][3]=a[3][0]=-1;a[0][4]=a[4][0]=-3;
	a[1][2]=a[2][1]=-3;a[1][3]=a[3][1]=-2;a[1][4]=a[4][1]=-4;
	a[2][3]=a[3][2]=-2;a[2][4]=a[4][2]=-2;
	a[3][4]=a[4][3]=-1;
	a[4][4]=0;
	memset(cost,0,sizeof(cost));
	cost[0][0]=0;
	for(i=1;i<=rlen;i++){
		int sum=0;
		for(int j=0;j<i;j++){
			sum+=a[4][get(rights[j])];
		}
		cost[0][i]=sum;
	//	cout<<"cost "<<0<<" "<<i<<"="<<cost[0][i]<<" ";
	}
	//cout<<endl;
	for(i=1;i<=llen;i++){
		int sum=0;
		for(int j=0;j<i;j++){
			sum+=a[get(lefts[j])][4];
		}
		cost[i][0]=sum;
	//	cout<<"cost "<<i<<" "<<0<<"="<<cost[i][0]<<" ";
	}
	//cout<<endl;

}

void print(){
	for(int i=0;i<=llen;i++){
		for(int j=0;j<=rlen;j++){
			cout<<cost[i][j]<<" ";
		}
		cout<<endl;
	}



}

void main(){
	//ifstream cin("data.txt");
	int testcase;
	cin>>testcase;
	for(int i=0;i<testcase;i++){
		cin>>llen;
		if(llen!=0)cin>>lefts;
		cin>>rlen;
		if(rlen!=0)cin>>rights;
		init();
		//cout<<lefts<<" "<<rights<<endl;
		cout<<cal(llen,rlen)<<endl;
		//print();
	}


}

• 强烈建议题目多给一些典型的数据，这样找错也方便！！！ (0) zhb_msqx 2007-08-23 11:25:54
• Re:还是 WA，找不出来什么地方错了： (29) vincentguo 2007-09-11 13:24:09
• cost那里没错的，是数组开小了，把数组开成cost[150][150],lefts[150],rights[150]就过了！ (0) kikif 2007-09-11 19:50:18