基因序列

656

#include "stdafx.h"
#include "iostream"
#include "string"
#define NUM 100
using namespace std;
int n=0;
char s1[NUM];
char s2[NUM];
char map[128];
int score[5][5]={{5,-1,-2,-1,-3},{-1,5,-3,-2,-4},{-2,-3,5,-2,-2},{-1,-2,-2,5,-1},{-3,-4,-2,-1,0}};
int gene[NUM][NUM];
int first,second;
int i,j,k;
int _tmain(int argc, _TCHAR* argv[])
{
	map['A']=0;map['C']=1;map['G']=2;map['T']=3;map['-']=4;
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>first>>s1;
		cin>>second>>s2;
		gene[0][0]=0;
		for( j=1;j<second;j++)
			gene[0][j]=gene[0][j-1]+score[4][map[s2[j-1]]];
		for( k=1;k<=first;k++)
			gene[k][0]=gene[k-1][0]+score[map[s1[k-1]]][4];
		int m1,m2,m3;
		for(j=1;j<=first;j++ )
		{
			for(k=1;k<=second;k++)
			{
				m1=gene[j-1][k]+score[map[s1[j-1]]][4];
				m2=gene[j][k-1]+score[4][map[s2[j-1]]];
				m3=gene[j-1][k-1]+score[map[s1[j-1]]][map[s2[k-1]]];
				gene[j][k]=max(m1,max(m2,m3));
			}
		}
		cout<<gene[first][second]<<endl;
	}
	system("pause");
	return 0;
}