在資訊科學上,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 字串 $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
編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |