pku1080.cpp

这是ACM 方面的资料 是PKU的 北京大学的出来的

#include <stdio.h>
#include <string.h>
#define SIZE 110

char a[SIZE], b[SIZE];
int v[SIZE][SIZE];

const int P[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 cTon(char x)
{
	if (x == 'A')
		return 0;
	if (x == 'C')
		return 1;
	if (x == 'G')
		return 2;
	if (x == 'T')
		return 3;
	return 4;
}

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

void Solve()
{
	int la, lb;
	int i, j;
	int x, y, z;
	scanf("%d %s", &la, a);
	scanf("%d %s", &lb, b);
	v[0][0] = 0;
	for (i = 1; i <= la; i++)
	{
		v[i][0] = v[i - 1][0] + P[cTon(a[i - 1])][4];
	}
	for (j = 1; j <= lb; j++)
	{
		v[0][j] = v[0][j - 1] + P[4][cTon(b[j - 1])];
	}
	for (i = 1; i <= la; i++)
	{
		for (j = 1; j <= lb; j++)
		{
			x = v[i - 1][j - 1] + P[cTon(a[i - 1])][cTon(b[j - 1])];
			y = v[i - 1][j] + P[cTon(a[i - 1])][4];
			z = v[i][j - 1] + P[4][cTon(b[j - 1])];
			v[i][j] = Max(x, Max(y, z));
		}
	}
	printf("%d\n", v[la][lb]);
}

int main()
{
	int T;
	scanf("%d", &T);
	while (T--)
		Solve();
	return 0;
}