APCS 病毒演化 (zerojudge f582)

發表於 更新於 分類於 ， 閱讀次數： 文章字數： 572 所需閱讀時間 ≈ 2 分鐘

題目網址

科學家發現了 \(n\) 種病毒，編號分別是 \(1\) 到 \(n\)，已知每一種病毒可以用一個 RNA 序列來表達，RNA 序列是一個長度為 \(m\) 的字串，其中包含 A、U、C、G、@等字元，其中 @ 為科學家沒觀察清楚的位置，可能為 A、U、C、G 其中任何一種。 科學家也研究出了這些病毒的演化關係，除了一個最原始的病毒以外，每一種病毒都是從另一個病毒演化而來的，這些病毒會構成一個樹狀結構的病毒族譜 (如圖)。 病毒族譜

解題思路：
這題我是用 DP 寫，並使用 DFS 從根遍歷整棵樹，在過程完成狀態轉移。
在寫這題的時候，最困難的應該就是要想怎麼定義狀態還有狀態轉移如何在 \(O(1)\) 內做出來，而首先按照題目可知，不同位置的字元，無論在哪個點都不受影響，而當該點的某個位置為 @時，其有機會是 A、U、C、G 任意一個，因此不妨定義 \(dp[i][j][k]\) 代表第 \(i\) 個陣列的第 \(j\) 個字元為 \(k\) 時的單點至葉子最小距離 (A, U, C, G 分別對應到 \(k = 1, 2, 3, 4\))，而當第 \(i\) 個陣列的第 \(j\) 個字元已經被定義時 (也就是不為 @時) 就將其餘的點設為極大值，而在狀態轉移時，就會是他各個小孩在四種狀態的值加上與他的距離 (就是看小孩當前狀態是否跟父母一樣，一樣距離就是 0 不一樣就是 1) 的最小值，以數學式表達如下：(其中 \(child\) 代表第 \(i\) 個陣列的小孩個數，\(child_p\) 代表第 \(i\) 個陣列第 \(p\) 的小孩) \[dp[i][j][k] = \sum_{p=1}^{child} min(dp[child_p][j][1] + (k != 1), dp[child_p][j][2] + (k != 2), dp[child_p][j][3] + (k != 3), dp[child_p][j][4] + (k != 4))\] 而最後答案就是： \[\sum_{j=0}^{m-1} min(dp[root][j][1], dp[root][j][2], dp[root][j][3], dp[root][j][4])\] 總複雜度為 \(O(nm)\)

🌟 在當沒有小孩時 (葉子)，其各點的 dp 除設為極大值的位置外，均為 0。

病毒演化 
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
#include <bits/stdc++.h>
#define Max 1000000

using namespace std;

int n, m;
int dp[1003][81][6];
// dp[i][j][k] 代表第i個陣列的第j個字元為k時的單點至葉子最小距離
// k=1,2,3,4代表A,U,C,G
// 當該點已經被是確認的點時（不為@）設其dp值為 Max
// dp[i][j][k] = Σmin(dp[i_child][j][1~4]+k!=1~4)
// if i no child: dp[i][j][k] = 0
map<char, int> get_index = {{'A',1},{'U',2},{'C',3},{'G',4}};
vector<int> child[1003];

int calculate(int idx, int num, int ch){
    if(dp[idx][num][ch] != -1) return dp[idx][num][ch];
    if(child[idx].empty()) return dp[idx][num][ch] = 0;
    dp[idx][num][ch] = 0;
    for(int i: child[idx]){
        int add = Max;
        for(int k = 1; k<=4; k++)
            add = min(add, (calculate(i, num, k) + (k!=ch)));
        dp[idx][num][ch] += add;
    }
    //cout << idx << ' ' << num << ' ' << ch << ": " << dp[idx][num][ch] << '\n';
    return dp[idx][num][ch];
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); 
    cin >> n >> m;
    int root_idx;
    string tmp;
    for(int i = 0, tmpI, tmpJ; i < n; i++){
        cin >> tmpI >> tmpJ;
        if(tmpI == tmpJ) root_idx = tmpI;
        else child[tmpJ].push_back(tmpI);
        cin >> tmp;
        for(int j = 0; j < m; j++){
            for(int k = 1; k <= 4; k++){
                dp[tmpI][j][k] = -1;
                if(tmp[j] != '@' && k != get_index[tmp[j]]) 
                    dp[tmpI][j][k] = Max;
            }
        }
    }
    int ans = 0;
    for(int j = 0; j< m; j++){
        int little_ans = Max;
        for(int k = 1; k <= 4; k++)
            little_ans=min(little_ans, calculate(root_idx, j, k));
        ans+=little_ans;
    }
    cout<<ans<<'\n';
    return 0;
}
AC的Submission～