hdu poj 1080 Human Gene Functions LCS 动态规划

题意：给定两DNA序列，在序列中任意位置可以插入-和另外一个碱基匹配，每种匹配有个分值，求匹配的最大分值

思路：用dp[I][j]代表放a中第I个，与放b中第j个字符时的最大分值。

什么都不放dp[0][0]=0

在a前面加上与b长度相同的‘-’，与b全部匹配

dp[0][I]=dp[0][I-1]+map[4][a[I-1]  (1=<I<=b.size)

在b前面加上与a长度相同的'-'，与a全部匹配

dp[I][0]=dp[I-1][0]+map[4][b[I-1] (1=<I<=a.size)

#include<cstdio>
#include<cstring>
#include<string>
#include<iostream>
using namespace std;
const int maxn =110;
int a[maxn],b[maxn];
int l1,l2;
int map[5][5]=
{
{5,-1,-2,-1,-3},//A 0 ,C 1,G 2 T 3 , - 4
{-1,5,-3,-2,-4},
{-2,-3,5,-2,-2},
{-1,-2,-2,5,-1},
{-3,-4,-2,-1,0}
};
int dp[maxn][maxn];
int Max(int a,int b,int c){int d=a>b?a:b;int e=c>d?c:d;return e;}
int main()
{
	int t;
	char c;
	while(scanf("%d",&t)!=EOF)
	{
	while(t--)
	{
		memset(dp,0,sizeof(dp));
		scanf("%d",&l1);
		getchar();
		for(int i=0;i<l1;i++)
		{
			scanf("%c",&c);
			if(c=='A')a[i]=0;
			if(c=='C')a[i]=1;
			if(c=='G')a[i]=2;
			if(c=='T')a[i]=3;
			if(c=='-')a[i]=4;
		}
		scanf("%d",&l2);
		getchar();
		for(int i=0;i<l2;i++)
		{
			scanf("%c",&c);
			if(c=='A')b[i]=0;
			if(c=='C')b[i]=1;
			if(c=='G')b[i]=2;
			if(c=='T')b[i]=3;
			if(c=='-')b[i]=4;
		}
		
		dp[0][0]=0;
		for(int i=1;i<=l1;i++)
		dp[i][0]=dp[i-1][0]+map[4][a[i-1]];
		for(int i=1;i<=l2;i++)
		dp[0][i]=dp[0][i-1]+map[4][b[i-1]];
		
		int x1,x2,x3;x1=x2=x3=0;
		for(int i=1;i<=l1;i++)
		for(int j=1;j<=l2;j++)
		{
			x1=dp[i-1][j]+map[4][a[i-1]];
			x2=dp[i][j-1]+map[4][b[j-1]];
			x3=dp[i-1][j-1]+map[a[i-1]][b[j-1]];
			dp[i][j]=Max(x1,x2,x3);
		}
		
		printf("%d\n",dp[l1][l2]);
	}
	}
	
}