学步园

Problem Address：http://poj.org/problem?id=1080

【思路】

一道LCS的变形。

设空格为0，A为1，C为2，G为3，T为4。

状态转移方程：dp[i][j] = max(dp[i-1][j-1]+value[a[i]][b[j]], dp[i-1][j]+value[a[i]][0], dp[i][j-1]+value[0][b[j]]);

对于边界，即三个值中有某些值无法取到时，将其忽视。

即：

dp[0][0] = 0;

dp[i][0] = dp[i-1][0] + value[a[i]][0];

dp[0][j] = dp[0][j-1] + value[0][b[j]];

【代码】

#include <iostream>
using namespace std;

const int maxn = 100;

int value[5][5] = {
{0, -3, -4, -2, -1},
{-3, 5, -1, -2, -1},
{-4, -1, 5, -3, -2},
{-2, -2, -3, 5, -2},
{-1, -1, -2, -2, 5}};

int dp[maxn+5][maxn+5];
char sa[maxn+5];
char sb[maxn+5];
int a[maxn+5];
int b[maxn+5];

inline int getcode(char c)
{
	if (c=='A') return 1;
	else if (c=='C') return 2;
	else if (c=='G') return 3;
	else if (c=='T') return 4;
	else return 0;
}

inline int max(int x, int y, int z)
{
	if (x<y) x=y;
	if (x<z) x=z;
	return x;
}

int main()
{
	int t;
	int la, lb;
	int i, j;
	scanf("%d", &t);
	while(t--)
	{
		scanf("%d %s", &la, sa);
		scanf("%d %s", &lb, sb);
		for (i=0; i<la; i++)//先转换为整型数组
			a[i+1] = getcode(sa[i]);
		for (i=0; i<lb; i++)
			b[i+1] = getcode(sb[i]);
		dp[0][0] = 0;//初始化各边界
		for (i=1; i<=la; i++)
			dp[i][0] = dp[i-1][0] + value[a[i]][0];
		for (j=1; j<=lb; j++)
			dp[0][j] = dp[0][j-1] + value[0][b[j]];
		for (i=1; i<=la; i++)//开始dp
		{
			for (j=1; j<=lb; j++)
			{
				dp[i][j] = max(dp[i-1][j-1]+value[a[i]][b[j]], dp[i-1][j]+value[a[i]][0], dp[i][j-1]+value[0][b[j]]);
			}
		}
		printf("%d\n", dp[la][lb]);
	}
	return 0;
}