d272. 11583 - Alien DNA
Tags :
Accepted rate : 69人/73人 ( 95% ) [非即時]
評分方式:
Tolerant

最近更新 : 2009-05-22 09:46

Content

外星人的DNA 比人類的DNA複雜很多。例如 外星人的DNA 不只是單單的固定的序列而是這個序列的各種集合,簡而言之,一個小寫字串的每一個字母都是不同的集合。

人類的只是單純A ,T, C, G在配對組合。 

 因為外星人的DNA比人類的DNA複雜很多,所以關於用在外星人的演算法也相對的比較複雜,然而你剛進去一家公司三天而已,不太能處理太複雜的工作。

你的工作很簡單。你必須發展出一套軟體來切外星人的DNA,並使切的刀數越少越好 ,每一個認定相同的DNA必須要只少有一個相同的集合。

Input

第一行代表有t(t ≤ 100)組測試資料,每一組測試資料有一個N(1 ≤ n ≤ 10,000) 代表有幾個DNA序列,接下來有N行包含一行字串小寫字母,代表一個序列,每一行的字串的字母都不會重複出現。每一個字串都只少有一個字母,有可能出現相同的字串。

 

Output
對於每一個測試資料,輸出一個所需最小的切的次數。
Sample Input #1
2
5
as
sd
df
fg
gh
3
plum
orange
plum

Sample Output #1
2
2
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (100%): 1.0s , <10M
Hint :

as sd | df fg | gh 切兩刀

as |sd df| fg gh 切兩刀

 as |sd | df| fg | gh 切四刀

plum | orange | plum

所以 最小要切兩刀

Tags:
出處:
UVa11583 [管理者: nanj0178 (nanj) ]

Status Forum 排行

ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」