3063121_ac_0ms_308k.c

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <string.h>

int mtr[][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 table(char a,char b)
{
	int i, j;
	char str[] = "ACGT-";

	for (i = 0; str[i]; i++)
	{
		if(str[i]==a)
			break;
	}
	for (j = 0; str[j]; j++)
	{
		if(str[j]==b)
			break;
	}
	return mtr[i][j];
}

int max(int a,int b)
{
	return a > b ? a : b;
}

int main()
{
	int n, c;
	int i, j;
	int l1, l2;
	char str1[202], str2[202];
	int array[202][202];

	scanf("%d",&n);
	for (c = 1; c <= n; c++)
	{
		scanf("%d%s%d%s",&l1,str1,&l2,str2);
		array[0][0] = 0;
		for(i = 1; i <= l1; i++)
		{
			array[0][i] = array[0][i-1]+table('-',str1[i-1]);
		}
		for(j = 1; j <= l2; j++)
		{
			array[j][0] = array[j-1][0]+table('-',str2[j-1]);
		}
		for(i = 1; i <= l2; i++)
		{
			for(j = 1; j <= l1; j++)
			{
				array[i][j] = max(array[i-1][j-1]+table(str1[j-1],str2[i-1]),max(array[i][j-1]+table(str1[j-1],'-'),array[i-1][j]+table(str2[i-1],'-')));
			}
		}
		printf("%d\n",array[l2][l1]);
	}
	return 0;
}