记录编号	35006	评测结果	AAAAAAAAAA
题目名称	相似基因	最终得分	100
用户昵称	Truth.Cirno	是否通过	通过
代码语言	C++	运行时间	0.003 s
提交时间	2012-02-13 21:32:39	内存使用	0.34 MiB

#include <cstdio>
using namespace std;

int sim[5][5]={{0}},f[110][110]={{0}};

int main(void)
{
	freopen("gene.in","r",stdin);
	freopen("gene.out","w",stdout);
	int i,j,la,lb,a[110]={0},b[110]={0},temp;
	char str[110];
	scanf("%d %[^\n]\n",&la,&str);
	for (i=1;i<=la;i++)
	{
		temp=i-1;
		if (str[temp]=='A')
			a[i]=1;
		else if (str[temp]=='C')
			a[i]=2;
		else if (str[temp]=='G')
			a[i]=3;
		else if (str[temp]=='T')
			a[i]=4;
		else
			a[i]=0;
	}
	scanf("%d %[^\n]\n",&lb,&str);
	for (i=1;i<=lb;i++)
	{
		temp=i-1;
		if (str[temp]=='A')
			b[i]=1;
		else if (str[temp]=='C')
			b[i]=2;
		else if (str[temp]=='G')
			b[i]=3;
		else if (str[temp]=='T')
			b[i]=4;
		else
			a[i]=0;
	}
	sim[1][1]=5;
	sim[1][2]=-1;
	sim[1][3]=-2;
	sim[1][4]=-1;
	sim[1][0]=-3;
	sim[2][1]=-1;
	sim[2][2]=5;
	sim[2][3]=-3;
	sim[2][4]=-2;
	sim[2][0]=-4;
	sim[3][1]=-2;
	sim[3][2]=-3;
	sim[3][3]=5;
	sim[3][4]=-2;
	sim[3][0]=-2;
	sim[4][1]=-1;
	sim[4][2]=-2;
	sim[4][3]=-2;
	sim[4][4]=5;
	sim[4][0]=-1;
	sim[0][1]=-3;
	sim[0][2]=-4;
	sim[0][3]=-2;
	sim[0][4]=-1;
	sim[0][0]=0;
	for (i=1;i<=la;i++)
		f[i][0]=f[i-1][0]+sim[a[i]][0];
	for (i=1;i<=lb;i++)
		f[0][i]=f[0][i-1]+sim[0][b[i]];
	for (i=1;i<=la;i++)
		for (j=1;j<=lb;j++)
		{
			f[i][j]=f[i-1][j-1]+sim[a[i]][b[j]];
			temp=f[i-1][j]+sim[a[i]][0];
			if (f[i][j]<temp)
				f[i][j]=temp;
			temp=f[i][j-1]+sim[0][b[j]];
			if (f[i][j]<temp)
				f[i][j]=temp;
		}
	printf("%d\n",f[la][lb]);
	fclose(stdin);
	fclose(stdout);
	return(0);
}