#include"iostream"
using namespace std;
#define Max_size  101
int f[Max_size][Max_size];
int max(int x,int y)
{
	return x>=y? x:y;
}
int Max(int x,int y,int z)
{
	return max(max(x,y),z);
}
int int1(char x)
{
	if(x=='A')
		return 0;
	if(x=='C')
		return 1;
	if(x=='G')
		return 2;
	if(x=='T')
		return 3;
	if(x=='-')
		return 4;
}
int value(char a,char b)
{
	
	char  value_list[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}
	};
   return value_list[int1(a)][int1(b)];

}
int main()
{
	int Test_case;
	cin>>Test_case;
	while(Test_case--)
	{
		int len1,len2;
		char str1[101],str2[101];
		memset(f,0,sizeof(f));
		cin>>len1>>str1;
		cin>>len2>>str2;
		for(int i=0;i<=len1;i++)
			for(int j=0;j<=len2;j++)
			{

		       if(i==0&&j==0)
				   f[i][j]=0;
			   else if(j==0)
			   {
				   f[i][j]=f[i-1][j]+value(str1[i-1],'-');
			   }
			   else if(i==0)
			   {
				   f[i][j]=f[i][j-1]+value('-',str2[j-1]);
			   }
			   else
			   {
				   f[i][j]=Max((f[i-1][j-1]+value(str1[i-1],str2[j-1])),(f[i-1][j]+value(str1[i-1],'-')),
					   (f[i][j-1]+value('-',str2[j-1])));
			   }
			}
			cout<<f[len1][len2]<<endl;
	}
	return 1;
}
    

• Re:一道用dp 做的题，有兴趣的来看看！ (1265) gdcc11 2009-05-02 19:34:00
  • 你处理0的时候出现了问题。。 (1390) 8ab12097207 2009-08-16 15:17:02