問題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1080思路:
想法與最長公共子序列類似
用f[i][j]表示str_a[1..i]與str_b[1..j]的相似度，而所求即f[len_a][len_b]，需要注意初始化部分的代碼
狀態轉移方程見代碼注釋
代碼:
1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<string.h>
4 #define MAX_LEN 101
5 #define INF 'I'
6 #define Score(ch_a, ch_b) (score[map[ch_a-'A']][map[ch_b-'A']])
7 int len_a, len_b;
8 char str_a[MAX_LEN+1], str_b[MAX_LEN+1];
9 int table[MAX_LEN][MAX_LEN];
10 const int score[][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,-65535}};
11 /* A C G I T */
12 const int map[] = {0,-1,1,-1,-1,-1,2,-1,4,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,3};
13
14 /*
15 * f[i][j] represent the similarity of str_a[1..i] and str_b[1..j], so:
16 * f[i][j] = max { f[i-1][j-1]+Score(str_a[i], str_b[j]),
17 * f[i-1][j] + Score(str_a[i], '-'),
18 * f[i][j-1] + Score('-', str_b[j]) }
19 */
20 int
21 dp()
22 {
23 int i, j, a, b, c, max;
24 /* Attention: Initialization */
25 table[0][0] = 0;
26 for(i=1; i<=len_a; i++)
27 table[i][0] = table[i-1][0] + Score(str_a[i], INF);
28 for(j=1; j<=len_b; j++)
29 table[0][j] = table[0][j-1] + Score(str_b[j], INF);
30
31 for(i=1; i<=len_a; i++) {
32 for(j=1; j<=len_b; j++) {
33 a = table[i-1][j-1] + Score(str_a[i], str_b[j]);
34 b = table[i-1][j] + Score(str_a[i], INF);
35 c = table[i][j-1] + Score(INF, str_b[j]);
36 max = a > b ? a : b;
37 max = c > max ? c : max;
38 table[i][j] = max;
39 }
40 }
41 return table[len_a][len_b];
42 }
43
44 int
45 main(int argc, char **argv)
46 {
47 int tests;
48 scanf("%d", &tests);
49 while(tests--) {
50 scanf("%d %s", &len_a, str_a+1);
51 scanf("%d %s", &len_b, str_b+1);
52 printf("%d\n", dp());
53 }
54 }