f582. 4. 病毒演化 - 高中生程式解題系統

內容

科學家發現了 $n$ 種病毒，編號分別是 $1$ 到 $n$ ，已知每一種病毒可以用一個RNA 序列來表達，RNA序列是一個長度為 $m$ 的字串，其中包含 A、U、C、G、@ 等字元，其中 @ 為科學家沒觀察清楚的位置，可能為 A、U、C、G 其中任何一種。

科學家也研究出了這些病毒的演化關係，除了一個最原始的病毒以外，每一種病毒都是從另一個病毒演化而來的，這些病毒會構成一個樹狀結構的病毒族譜(如圖)。

兩個 RNA 序列的的距離定義為它們的漢明距離，也就是相異的位數個數。更具體的說，對於兩個長度都是 $m$ 的 RNA 序列 $a, b$ ，它們的漢明距離就是有幾個位置 $i$ 滿足 $a_{i} \neq b_{i}$ 。

你想知道目前的病毒族譜的每一個 RNA 序列中的 @ 字元的填入 A、U、C、G 中的其中一個字元後，每一個病毒與它演化來源的病毒的距離總合最小值是多少?

輸入說明

第一行包含兩個正整數 $n, m (1 \leq n \leq 1000, 1 \leq m \leq 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

範例輸入 #2

範例輸出 #2

測資資訊：

記憶體限制： 256 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

提示：

標籤:

APCS DP tree

出處:

2020年7月 APCS [管理者： edison1998402@gmail.com

cthbst (吳宗達) ]

編號	身分	題目	主題	人氣	發表日期
37843	edoctopus322 ... (Moon Jam)	f582	解題思路（含一些小技巧）	801	2023-10-13 21:27