noj 1080 lcs的变形题.txt

ACM资料大集合

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
#include <vector>
#include <iterator>
using namespace std;
#define PB push_back

//NOJ 1080 LCS的变形题
#define NMAX 105
char a[NMAX],b[NMAX];

int score[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,-100}};
int f[NMAX][NMAX];

int getmax(int aa,int bb,int cc)
{
	int max;
	if(aa<bb) max=bb;
	else max=aa;
	if(max<cc) return cc;
	else return max;
}
int trans(char x)
{
	switch(x)
	{
		case 'A': return 0;
		case 'C': return 1;
		case 'G': return 2;
		case 'T': return 3;
		case ' ': return 4;
	}
}
int gets(char aa,char bb)
{
	int aaa,bbb;
	aaa=trans(aa);
	bbb=trans(bb);
	return score[aaa][bbb];
}

void print(int anum,int bnum)
{
	int i,j;
	for(i=0;i<=anum;i++)
	{
		for(j=0;j<=bnum;j++)
		{
			printf("%3d",f[i][j]);
		}
		printf("\n");
	}
}
int cal(int anum,int bnum)
{
	int i,j;
	f[0][0]=0;
	for(i=1;i<=anum;i++)
	{
		f[i][0]=f[i-1][0]+gets(a[i-1],' ');
	}
	for(i=1;i<=bnum;i++)
	{
		f[0][i]=f[0][i-1]+gets(b[i-1],' ');
	}
	for(i=1;i<=anum;i++)
	{
		for(j=1;j<=bnum;j++)
		{
			f[i][j]=getmax(f[i-1][j-1]+gets(a[i-1],b[j-1]),f[i-1][j]+gets(a[i-1],' '),f[i][j-1]+gets(' ',b[j-1]));
		}
	}
//	print(anum,bnum);
	return f[anum][bnum];
}

int main()
{
	int i,cnum,anum,bnum;
	scanf("%d",&cnum);
	for(i=1;i<=cnum;i++)
	{
		scanf("%d %s",&anum,&a);
		scanf("%d %s",&bnum,&b);
		printf("%d\n",cal(anum,bnum));
	}
	return 0;
}