解題區►解題區 - UVa

UVa 1182 - Sequence Alignment

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

基因對齊的最大匹配問題，或者是說 minimum edit distance，最小編輯距離。

花費方案

  • 連續個 - 獲益 -1，也就是 ----- = -1、a--b--c = -2
  • 對齊 a - a 獲益 2。
  • 不對 a - b 獲益 0。 (這一個對法，題目沒有講，因此很容易掛 WA。)

Sample Input

1
2
3
4
5
2
AADDEFGGHC 
ADCDEGH 
ERTTHCBYNQC 
BEARTBCHQYN

Sample Output

1
2
9 
8

Solution

狀態 dp[i][j][a_str or b_str][prev gap/ no prev gap]

先將 a, b 反轉，靠右對齊不是重點！

考慮 a 字串 i 位置匹配到 b 字串 j 位置，然後考慮尾端的狀態，要不兩個都是字符，要不其中一個是 - 產生的 gap，而這個 gap 可能在 a 字串或者是 b 字串，如果已經存在 gap，放置時則不需要花費，反之額外增加花費。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <stdio.h> 
#include <string.h>
#include <algorithm>
#include <assert.h>
using namespace std;
void inv(char s[], int n) {
	for (int i = 0, j = n-1; i < j; i++, j--)
		swap(s[i], s[j]);
}
int dp[64][64][2][2];
int main() {
	int testcase;
	char s1[64], s2[64];
	scanf("%d", &testcase);
	while (getchar() != '\n');
	while (testcase--) {
		gets(s1);
		gets(s2);
		int n1 = strlen(s1), n2 = strlen(s2);
		inv(s1, n1), inv(s2, n2);
		for (int i = 0; i <= n1; i++) {
			for (int j = 0; j <= n2; j++) {
				dp[i][j][0][0] = dp[i][j][0][1] = -0x3f3f3f3f;
				dp[i][j][1][0] = dp[i][j][1][1] = -0x3f3f3f3f;
			}
		}
		dp[0][0][0][1] = 0;
		dp[0][0][1][1] = 0;
		int ret = -0x3f3f3f3f;
		for (int i = 0; i <= n1; i++) {
			for (int j = 0; j <= n2; j++) {
				int v = max(dp[i][j][0][0], dp[i][j][0][1]);
				v = max(v, max(dp[i][j][1][0], dp[i][j][1][1]));
				dp[i+1][j+1][0][1] = max(dp[i+1][j+1][0][1], v);
				dp[i+1][j+1][1][1] = max(dp[i+1][j+1][1][1], v);
				if (s1[i] == s2[j]) {
					dp[i+1][j+1][0][1] = max(dp[i+1][j+1][0][1], v + 2);
					dp[i+1][j+1][1][1] = max(dp[i+1][j+1][1][1], v + 2);
				}
				dp[i+1][j][0][0] = max(dp[i+1][j][0][0], dp[i][j][0][0]);
				dp[i+1][j][0][0] = max(dp[i+1][j][0][0], dp[i][j][1][0] - 1);
				dp[i+1][j][0][0] = max(dp[i+1][j][0][0], dp[i][j][0][1] - 1);
				dp[i+1][j][0][0] = max(dp[i+1][j][0][0], dp[i][j][1][1] - 1);
				
				dp[i][j+1][1][0] = max(dp[i][j+1][1][0], dp[i][j][1][0]);
				dp[i][j+1][1][0] = max(dp[i][j+1][1][0], dp[i][j][0][0] - 1);
				dp[i][j+1][1][0] = max(dp[i][j+1][1][0], dp[i][j][0][1] - 1);
				dp[i][j+1][1][0] = max(dp[i][j+1][1][0], dp[i][j][1][1] - 1);
				if (j == n2 || i == n1) {
					ret = max(ret, max(dp[i][j][0][0], dp[i][j][0][1]));
					ret = max(ret, max(dp[i][j][1][0], dp[i][j][1][1]));
				}
			}
		}
		printf("%d\n", ret);
	}
	return 0;
}
/*
2
AADDEFGGHC
ADCDEGH
ERTTHCBYNQC
BEARTBCHQYN
3
ABC
ABC
ABC
AC
BAC
AC
*/