解題區/解題區 - UVa

UVa 10185 - Phylogenetic Trees Inherited

contents

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

Problem

給 n 個化合物，每個化合物長度 m。其中 n 為 2 的冪次。

建造一個分類的關係樹，每一個節點上會有分類依據長度依舊為 m，而每一個化合物按照輸入順序成為完滿樹的葉節點。

目標這個樹的花費越少越好，樹花費的計算為相鄰兩個節點之間的漢明碼距離總和。也就是與子節點所表示的字串之間有多少不同的字符。

Sample Input

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
4 3
AAG
AAA
GGA
AGA
  
4 3
AAG
AGA
AAA
GGA 
  
4 3
AAG
GGA
AAA
AGA
  
4 1
A
R
A
R
  
2 1
W
W
  
2 1
W
Y
  
1 1
Q
  
0 0

Sample Output

1
2
3
4
5
6
7
AGA 3
AGA 4
AGA 4
R 2
W 0
Y 1
Q 0

Solution

事實上，我們可以分開考慮 m 位的結果，彼此之間的花費最小化即可。

當只考慮要填什麼的時候，如果兩個子樹填法有所交集，則表示選擇其中一個，與其子節點都不需要花費，如果是空集，則必然選擇其中一個子樹結果來補足，花費多 1。

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
#include <stdio.h>
char acid[1024][1024], ret[2048];
int main() {
    int n, m;
    while (scanf("%d %d", &n, &m) == 2 && n) {
        for (int i = 0; i < n; i++)
            scanf("%s", acid[i]);
        ret[m] = '\0';
        int diff = 0, N = 2 * n;
        for (int i = 0; i < m; i++) {
            int dp[2048] = {};
            for (int j = n; j < N; j++)
                dp[j] = 1<<(acid[j - n][i] - 'A');
            for (int j = n-1; j > 0; j--) {
                dp[j] = dp[j<<1]&dp[j<<1|1];
                if (dp[j] == 0) { // choose one branch, cost 1
                    diff++;
                    dp[j] = dp[j<<1]|dp[j<<1|1];
                }
            }
            for (int j = 0; j < 26; j++) {
                if ((dp[1]>>j)&1) {
                    ret[i] = j + 'A';
                    break;
                }
            }
        }
        printf("%s %d\n", ret, diff);
    }
    return 0;
}