在資訊科學上，RNA 病毒可以看成一個由 A、U、G、C 這四種字母構成的字串。病毒演化中，某些字元可能變異成其他字元，例如將 AAUGG 中的第 3 個位置的 U 換成 C， 則得到 AACGG，變異可能發生在多個位置。有個實驗團隊取得了某種 RNA 病毒的數 個 RNA 片段樣本，並且掌握到這些樣本演化的親緣關係，用
（樣本編號，親代編號，RNA 字串）
的格式記錄，其中「樣本編號」與「親代編號」為兩個整數，若兩數字相同，則該樣 本即為演化的源頭。例如，
（1, 1, AAAA）
（2, 1, GCAA）
表示樣本 1 的 RNA 字串為 AAAA，樣本 2 的為 GCAA，且樣本 2 是由樣本 1 在兩個位 置發生變異演化而來，樣本 1 為演化的源頭。
然而，字串中每個位置的字元無法確定，實驗團隊以@來表示這些字元，換言之，@可能為 A、U、G、C 中任何一個。請注意，一個字串中可能有多個@，並非代表這些位 置的字元是相同的。例如 A@C@可能是任何第一個字元為 A 且第三個字元為 C 的字 串，像是 ACCU 或 AACC。團隊猜測演化過程發生的變異總數會盡可能的少。請你利 用親緣關係，來計算最小的變異總數量。
第一行有兩個正整數 $n$ 與 $m$，表示共有 $n$ 個樣本，由 $1 \sim n$ 編號；每個樣本之 RNA 字串長度均為 $m$，其中 $n \le 1000$ 且 $m \le 80$。
接下來 $n$ 行，每行包 含以空白間隔的兩個正整數 $i$ 與 $j$ 以及一個 RNA 字串 $s_i$，對應一個樣本$(i, j, s_i)$，$s_i$ 由 A、U、G、C 與@五種字元所組成。若 $i=j=1$，則該樣本即為演化的源頭， 源頭以外的樣本皆恰有一個親代。
輸出最小可能的變異總數。
2 3 1 1 AAC 2 1 A@@
0
6 1 1 1 @ 2 1 @ 3 1 C 4 1 C 5 2 A 6 2 A
1
公開 測資點#0 (20%): 1.0s , <1M
公開 測資點#1 (20%): 1.0s , <1M
公開 測資點#2 (20%): 1.0s , <1M
公開 測資點#3 (20%): 1.0s , <1M
公開 測資點#4 (20%): 1.0s , <1M
範例一說明：樣本 2 為 AAC 時，變異量為 0。
範例二說明：我們以一樹狀結構表示此例的親緣關係：
將樣本 1 置換成 C、樣本 2 置換成 A，則只有在樣本 1 與 2 之間有一個變異，其它皆 無變異，故答案是 1。
提示：從範例二看到的第一件事是這些 RNA 是個樹狀結構，另外一個很重要的事情是：雖然每個點是個字串，但是字串的每個位置是獨立的，也就是所有字串的第 1 個字元，要算一個最小變異量；所有字串的第 2 個字元，要算一個最小變異量；對每一個字串位置 $i$ 都要算一個最小變異量，最後的答案是把他們加起來。所以，我們只要會解字串長度 $m=1$ 的狀況，最後套一個迴圈就好了。
如果沒有’@’，所有的變異都是確定的，只要把每個點與它的 parent 比較是否相等就好了，所以問題在如何決定’@’變異量。如果葉節點是’@’，我們可以讓它跟它的 parent 相同，這顯然不會有變異量，也就是說是’@’的葉子根本可以無視它。為了計算方便，我們先將 AUCG 轉換為數字 0~3，以 DP 的觀點，對於每個節點 $v$，我們算四個成本 $cost[v][i]$, $i$ 從 $0 \sim 3$，分別代表如果 parent 的字元是 $i$ 的時候 $v$ 點以 下子樹的總成本，然後去建構出遞迴式。
| ID | User | Problem | Subject | Hit | Post Date |
沒有發現任何「解題報告」 |
|||||