1027.cpp

自己的ac代码 在acm.zju.edu.cn 上的题目

#include<stdio.h>
int value(char a,char b)
{
	int v[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 aa;int bb;
	if(a=='A')aa=0;
	else if(a=='C')aa=1;
	else if(a=='G')aa=2;
	else if(a=='T')aa=3;
	else aa=4;

	if(b=='A')bb=0;
	else if(b=='C')bb=1;
	else if(b=='G')bb=2;
	else if(b=='T')bb=3;
	else bb=4;
	return v[aa][bb];
}

int opt[200][200];		

int main()
{
	int T,t;
	int i,j,k;
	scanf("%d",&T);
	for(t=1;t<=T;t++)
	{
		int la,lb;
		char sa[1000],sb[1000];
		scanf("%d%s",&la,sa);
		scanf("%d%s",&lb,sb);
		for(i=0;i<=la;i++)
			for(j=0;j<=lb;j++)
			{
				if(i==0 && j==0) opt[i][j]=0;
				else if(i==0 )opt[i][j]=opt[i][j-1]+value('-',sb[j-1]);
				else if(j==0)opt[i][j]=opt[i-1][j]+value(sa[i-1],'-');
				else
				{
					int v1=opt[i-1][j-1]+value(sa[i-1],sb[j-1]);
					int v2=opt[i-1][j]+value(sa[i-1],'-');
					int v3=opt[i][j-1]+value('-',sb[j-1]);
					if(v1>=v2 && v1>=v3)opt[i][j]=v1;
					if(v2>=v1 && v2>=v3)opt[i][j]=v2;
					if(v3>=v1 && v3>=v2)opt[i][j]=v3;
				}
			}
			printf("%d\n",opt[la][lb]);
	}
	return 0;
}