[동적 기획 DP,2 차원 동 귀]poj 1080,Human Gene Functions

# include<iostream>
using namespace std;

# define N 103
char a[N],b[N];
int r[N][N];

int match[N][N];

void Init()
{
    match['A']['A']=match['C']['C']=match['G']['G']=match['T']['T']=5;
    match['A']['C']=match['C']['A']=match['A']['T']=match['T']['A']=match[' ']['T']=match['T'][' ']=-1;
    match['A']['G']=match['G']['A']=match['C']['T']=match['T']['C']=match['G']['T']=match['T']['G']=match['G'][' ']=match[' ']['G']=-2;
    match['A'][' ']=match[' ']['A']=match['C']['G']=match['G']['C']=-3;
    match['C'][' ']=match[' ']['C']=-4;
}

int main()
{
	int t,i,j,k,l1,l2,t1,t2;
	Init();

	cin>>t;
	for(i=1;i<=t;i++)
	{
		r[0][0]=0;
		cin>>l1;
		for(j=1;j<=l1;j++)
		{
			cin>>a[j];
			r[j][0]=r[j-1][0]+match[a[j]][' '];
		}
		cin>>l2;
		for(k=1;k<=l2;k++)
		{
			cin>>b[k];
			r[0][k]=r[0][k-1]+match[' '][b[k]];
		}

		for(j=1;j<=l1;j++)
		{
			for(k=1;k<=l2;k++)
			{
				/*
				if(a[j]==b[k])
				{
					r[j][k]=r[j-1][k-1]+match[a[j]][b[k]];
				}
				else
				{
					t1=r[j-1][k]+match[a[j]][' '];
					t2=r[j][k-1]+match[' '][b[k]];
					r[j][k] = t1>t2? t1:t2;
				}
				*/
				r[j][k]=r[j-1][k-1]+match[a[j]][b[k]];
				r[j][k]= r[j][k]>r[j-1][k]+match[a[j]][' ']? r[j][k]:r[j-1][k]+match[a[j]][' '];
				r[j][k]= r[j][k]>r[j][k-1]+match[' '][b[k]]? r[j][k]:r[j][k-1]+match[' '][b[k]];
			}
		}
		cout<<r[l1][l2]<<endl;
	}
	return 0;
}