內容
科學家發現了 n 種病毒，編號分別是 1 到 n，已知每一種病毒可以用一個 RNA 序列來表達，RNA 序列是一個長度為 m 的字串，其中包含 A、U、C、G、@ 等字元，其中 @ 為科學家沒觀察清楚的位置，可能為 A、U、C、G 其中任何一種。
科學家也研究出了這些病毒的演化關係，除了一個最原始的病毒以外，每一種病毒都是從另一個病毒演化而來的，這些病毒會構成一個樹狀結構的病毒族譜(如圖)。
兩個 RNA 序列的的距離定義為它們的漢明距離，也就是相異的位數個數。更具體的說，對於兩個長度都是 m 的 RNA 序列 a,b，它們的漢明距離就是有幾個位置 i 滿足 ai≠bi。
你想知道目前的病毒族譜的每一個 RNA 序列中的 @ 字元的填入 A、U、C、G 中的其中一個字元後，每一個病毒與它演化來源的病毒的距離總合最小值是多少?
輸入說明
第一行包含兩個正整數 n,m(1≤n≤1000,1≤m≤80)。
接下來 n 行，每行表示一種病毒，包含兩個整數 i,j 與一個字串 s，表示編號 i 的病毒是從編號 j 的病毒演化而來的，且編號 i 的病毒的 RNA 序列為 s。若編號 i 的病毒是最原始的病毒，則 j=i，保證這樣的病毒只會有一個。
配分
- 20分: RNA 序列中沒有 @，每個病毒都滿足 j<i。
- 40分: 每個病毒都滿足 j<i。
- 40分: 同原題目限制。
輸出說明
輸出每種病毒到它演化來源的病毒的距離總和最小值。
範例輸入
#1
2 3 1 1 AAC 2 1 A@@
範例輸出
#1
0
範例輸入
#2
6 1 1 1 @ 2 1 @ 3 1 C 4 1 C 5 2 A 6 2 A
範例輸出
#2
1
測資資訊：
記憶體限制：
64
MB
公開 測資點#0 (5%): 0.5s , <1M
公開 測資點#1 (5%): 0.5s , <1M
公開 測資點#2 (5%): 0.5s , <1M
公開 測資點#3 (5%): 0.5s , <1M
公開 測資點#4 (5%): 0.5s , <1M
公開 測資點#5 (5%): 0.5s , <1M
公開 測資點#6 (5%): 0.5s , <1M
公開 測資點#7 (5%): 0.5s , <1M
公開 測資點#8 (5%): 0.5s , <1M
公開 測資點#9 (5%): 0.5s , <1M
公開 測資點#10 (5%): 0.5s , <1M
公開 測資點#11 (5%): 0.5s , <1M
公開 測資點#12 (5%): 0.5s , <1M
公開 測資點#13 (5%): 0.5s , <1M
公開 測資點#14 (5%): 0.5s , <1M
公開 測資點#15 (5%): 0.5s , <1M
公開 測資點#16 (5%): 0.5s , <1M
公開 測資點#17 (5%): 0.5s , <1M
公開 測資點#18 (5%): 0.5s , <1M
公開 測資點#19 (5%): 0.5s , <1M
公開 測資點#0 (5%): 0.5s , <1M
公開 測資點#1 (5%): 0.5s , <1M
公開 測資點#2 (5%): 0.5s , <1M
公開 測資點#3 (5%): 0.5s , <1M
公開 測資點#4 (5%): 0.5s , <1M
公開 測資點#5 (5%): 0.5s , <1M
公開 測資點#6 (5%): 0.5s , <1M
公開 測資點#7 (5%): 0.5s , <1M
公開 測資點#8 (5%): 0.5s , <1M
公開 測資點#9 (5%): 0.5s , <1M
公開 測資點#10 (5%): 0.5s , <1M
公開 測資點#11 (5%): 0.5s , <1M
公開 測資點#12 (5%): 0.5s , <1M
公開 測資點#13 (5%): 0.5s , <1M
公開 測資點#14 (5%): 0.5s , <1M
公開 測資點#15 (5%): 0.5s , <1M
公開 測資點#16 (5%): 0.5s , <1M
公開 測資點#17 (5%): 0.5s , <1M
公開 測資點#18 (5%): 0.5s , <1M
公開 測資點#19 (5%): 0.5s , <1M
提示 ：
標籤:
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||