1316.cpp

哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码

/*  This Code is Submitted by wywcgs for Problem 1316 on 2006-02-02 at 01:13:44 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX = 128;
const char *CODE = "ACGT-";
const int MATCH[][5] = { { 5, -1, -2, -1, -3 }, { -1, 5, -3, -2, -4 }, 
								{ -2, -3, 5, -2, -2 }, { -1, -2, -2, 5, -1 } };

int match(char, char);

int main()
{
	int t, T, i, j;
	int l[2], best[MAX][MAX] = { { 0 } };
	char gene[2][MAX];

	scanf("%d", &T);
	for(t = 0; t < T; t++) {
		for(i = 0; i < 2; i++) scanf("%d %s", &l[i], gene[i]);
		for(i = 0; i < l[1]; i++) best[0][i+1] = best[0][i]+match(gene[1][i], '-');
		for(i = 0; i < l[0]; i++) {
			best[i+1][0] = best[i][0] + match(gene[0][i], '-');
			for(j = 0; j < l[1]; j++) {
				best[i+1][j+1] = max(best[i][j+1]+match(gene[0][i], '-'), best[i+1][j]+match(gene[1][j], '-'));
				best[i+1][j+1] = max(best[i+1][j+1], best[i][j]+match(gene[0][i], gene[1][j]));
			}
		}
		printf("%d\n", best[l[0]][l[1]]);
	}
	
	return 0;
}

int match(char a, char b)
{
	int oa, ob;
	for(oa = 0; CODE[oa] != a; oa++) ;
	for(ob = 0; CODE[ob] != b; ob++) ;
	return MATCH[oa][ob];
}