在資訊科學上，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 至 n 編號；每 個樣本之 RNA 字串長度均為 m，其中 n ≤ 1000 且 m ≤ 80。
接下來 n 行，每行包含以空白間隔的兩個正整數 i 與 j 以及一個 RNA 字串 si，對應一個樣本（i, j, si），si由 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 到 3，分別代表如果 parent 的字元是 i 的時候 v 點以 下子樹的總成本，然後去建構出遞迴式。
| ID | User | Problem | Subject | Hit | Post Date |
沒有發現任何「解題報告」 |
|||||