#include <stdio.h>

#define M(a,b,c) ( ( ((a)>(b))?(a):(b))>(c) )?(((a)>(b))?(a):(b)):(c)

int N,i,j,n1,n2;
char A[2][101];

int Judge(char A,char B);

void main()
{
  	scanf("%d\n",&N);
  	while (N--)
  	{
  		int DP[2][101]= {0};
  		int score = 0;
  		scanf("%d",&n1);
			if(n1)
				scanf("%s",A[0]);
		scanf("%d",&n2);
			if(n2)
				scanf("%s",A[1]);
		for(j = 1;j<=n2;++j)
			DP[0][j] = DP[0][j-1] + Judge(A[1][j-1],'_'); 
  		for (i = 1;i<=n1;++i){
			DP[(i)%2][0] =DP[(i-1)%2][0] + Judge(A[0][i-1],'_');
  			for (j = 1;j<=n2;++j){
   				if(A[0][i-1] == A[1][j-1]){
   					DP[i%2][j] = DP[(i-1)%2][j-1] + 5;
   				}
   				else{
  					DP[(i)%2][j] = M(
						( DP[(i-1)%2][j-1]+Judge(A[0][i-1],A[1][j-1]) ),			
						( DP[(i)%2][j-1] + Judge(A[1][j-1], '_')),
						( DP[(i-1)%2][j] + Judge(A[0][i-1],'_') )
					);
	  				}
  			}
  		}
  		printf("%d\n",DP[(n1)%2][n2]);
  	}
}

int Judge(char A,char B)
{
	switch(A)
	{
	case 'A':
		switch(B)
		{
		case 'A':
			return 5;
		case 'C':
			return -1;
		case 'G':
			return -2;
		case 'T':
			return -1;
		case '_':
			return -3;
		}
	case 'C':
		switch(B)
		{
		case 'C':
			return 5;
		case 'A':
			return -1;
		case 'G':
			return -3;
		case 'T':
			return -2;
		case '_':
			return -4;
		}
	case 'G':
		switch(B)
		{
		case 'G':
			return 5;
		case 'C':
			return -3;
		case 'A':
			return -2;
		case 'T':
			return -2;
		case '_':
			return -2;
		}
	case 'T':
		switch(B)
		{
		case 'T':
			return 5;
		case 'C':
			return -2;
		case 'G':
			return -2;
		case 'A':
			return -1;
		case '_':
			return -1;
		}
	case '_' :
		switch(B)
		{
		case 'C':
			return -4;
		case 'G':
			return -2;
		case 'T':
			return -1;
		case 'A':
			return -3;
		}
	}
}

• Re:呼……为了弄那个得分表格弄了N长的代码……不过省了空间……160K 0ms (725) cotton 2011-01-25 15:07:15