4837012_tle.cpp

来自「部分PKU上的源码」· C++ 代码 · 共 79 行

#include<iostream>
using namespace std;
char x[220];
char y[220];
int xl,yl;
int s[220][220];
int huo[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 result;
int getnum(char x)
{
	switch(x)
	{
	case 'A':return 0;
	case 'C':return 1;
	case 'G':return 2;
	case 'T':return 3;
	case 'K':return 4;
	}
	return -1;
}
int getit(char x,char y)
{
	int xh=getnum(x);
	int yh=getnum(y);
	return huo[xh][yh];
}
void testout()
{
	int i,j;
	for(i=0;i<yl;i++)
	{for(j=0;j<xl;j++) cout<<s[i][j]<<" ";cout<<endl;}
}
int main()
{
	int testnumber,i,j,k,l;
	cin>>testnumber;
	for(int count=0;count<testnumber;count++)
	{
		memset(s,0,sizeof(s));
		result=-100000;
		cin>>xl;
		x[0]='K';
		xl*=2;xl++;
		for(i=1;i<xl;i++) 
		{
			cin>>x[i++];
			x[i]='K';
		}
		cin>>yl;
		for(i=0;i<yl;i++)cin>>y[i];
		//i==0
		int temp=0;
		for(i=0;i<xl;i++)
		{
			s[0][i]=temp+getit(y[0],x[i]);
			temp+=getit('K',x[i]);
		}
		for(i=1;i<yl;i++)
		{
			for(j=0;j<xl;j++)
			{
				int lmax=-100000;
				for(k=0;k<j;k++) 
				{
					temp=s[i-1][k];
					for(l=k+1;l<j;l++) temp+=getit(x[l],'K');
					if(temp>lmax) lmax=temp;
				}
				if(x[j]=='K') if(s[i-1][j]>lmax) lmax=s[i-1][j];
				s[i][j]=lmax+getit(x[j],y[i]);
			}
		}
		//testout();
		result=-100000;
		for(i=0;i<xl;i++)if(result<s[yl-1][i]) result=s[yl-1][i];
		cout<<result<<endl;
	}
	return 0;
}