hdu 1080 Human Gene Functions

Problem

acm.hdu.edu.cn/showproblem.php?pid=1080

Meaning

给出一个二维表 similarity[][]，表示对应核苷酸配对时的相似度值，横杠 '-' 表示用空格代替一个核苷酸。

给出两个DNA序列 a[] 和 b[]，可以任意添加空格，但不能空格对空格。求两串的最大相似度。

Analysis

dp[i][j]：第一串前 i 个和第二串前 j 个配出的最大相似度

在考虑 dp[i][j] 时，a[i] 可能和 b[1] ~ b[j] 的任意一个配，或者一个都不配；b[j] 也可以和 a[1] ~ a[i] 的任何一个配，或一个都不配。

当 a[i] 和 b[k] 配对时，b[k+1] ~ b[j] 的就只能和空格配。

状态转移：dp[i][j] = max { dp[i][0] + dp[0][j] , dp[i-1][s-1] + sim[ a[i] ][ b[s] ] + sum , dp[t-1][j-1] + sim[ a[t] ][ b[j] ] + sum }

其中 sum 表示 b[s+1] ~ b[j] 都和空格配，或 a[t+1] ~ a[i] 都和空格配的总相似度。

注意 a[i] 要和 b[1] ~ b[j] 都匹配一次，b[j] 也要和 a[1] ~ a[i] 都匹配一次。

dp[i][0] 表示第一串前 i 个都和空格配的总相似度；dp[0][j] 类似。

为了好用那个表，可以对DNA串进行格式化，把 A 变成 0，C 变成 1…，空格是 4。

Source code

#include <stdio.h>
#define N 100
#define BIG 12345
#define NUC 4 /* nucleotides */

const int c[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, -BIG}
};
char a[N+3], b[N+3];
int aa[N+1], bb[N+1], dp[N+1][N+1];

void format(char *s, int *d, int l)
{
	for( ; l; --l)
		if(s[l] == 'A')
			d[l] = 0;
		else if(s[l] == 'C')
			d[l] = 1;
		else if(s[l] == 'G')
			d[l] = 2;
		else if(s[l] == 'T')
			d[l] = 3;
}

int max(int x, int y)
{
	return x > y ? x : y;
}

int main()
{
	int t;
	scanf("%d", &t);
	while(t--)
	{
		int la, lb, i, j;
		scanf("%d %s %d %s", &la, a+1, &lb, b+1);
		format(a, aa, la);
		format(b, bb, lb);

		dp[0][0] = 0;
		for(i=1; i<=la; ++i)
			dp[i][0] = dp[i-1][0] + c[aa[i]][NUC];
		for(j=1; j<=lb; ++j)
			dp[0][j] = dp[0][j-1] + c[NUC][bb[j]];

		for(i=1; i<=la; ++i)
			for(j=1; j<=lb; ++j)
			{
				int cnt = 0, k;
				// a[]前i个全和空格配，b[]前j个也全和空格配
				dp[i][j] = dp[i][0] + dp[0][j];
				// a[i]和b[1] ~ b[j]配
				for(k=j; k; --k)
				{
					dp[i][j] = max(dp[i][j],
						dp[i-1][k-1] + c[aa[i]][bb[k]] + cnt);
					cnt += c[NUC][bb[k]];
				}
				// b[j]和a[1] ~ a[i]配
				cnt = 0;
				for(k=i; k; --k)
				{
					dp[i][j] = max(dp[i][j],
						dp[k-1][j-1] + c[aa[k]][bb[j]] + cnt);
					cnt += c[aa[k]][NUC];
				}
			}
		printf("%d\n", dp[la][lb]);
	}
	return 0;
}