UOJ Logo Universal Online Judge

UOJ

#494. DNA序列

统计

2018年10月,MIT建立了最新的纳米科技研究中心MIT.nano。此后,不断有新的研究成果在此产生。

有一天,研究者发现了一种新的生物,这种生物的基因中含有$n$条DNA序列,每一条都有一定的长度,科学家们可以将每条DNA序列切断,从而取出它的一个非空前缀。此后,他们可以将这些前缀按任意顺序连结起来形成一条完整的DNA序列,这样的DNA序列对治疗癌症有很大的作用。

每条DNA序列都仅包含大写字母“A”,“C”,“G”,“T”。

科学家们很快发现,DNA序列的字典序越小,则治疗癌症的效果越好,他们想知道给定$n$条DNA序列,他们能获得的字典序最小的DNA序列是什么。

输入格式

第一行一个正整数$n$,表示DNA序列的个数。

接下来$n$行,每行一个非空字符串表示一条DNA,保证每个字符均为“A”,“C”,“G”,“T”中的一个。

输出格式

输出一行一个字符串,表示能获得的字典序最小的DNA序列。

样例一

input

5
AGT
GTA
ATC
GGGGG
CAT

output

AACAGG

explanation

五条DNA序列分别取前缀“A”,“G”,“A”,“G”,“CA”,按照“A+A+CA+G+G”的顺序拼接起来即可获得答案。

样例二

样例数据下载,满足存在一种最优解是按照1到$n$的顺序。

限制与约定

设$m$为所有字符串长度的最大值。

对于 $10\%$ 的数据,$m = 1$。

对于 $30\%$ 的数据,$n, m \le 7$。

对于另外 $30\%$ 的数据,满足存在一种最优解是按照1到$n$的顺序。

对于 $100\%$ 的数据,$1 \le n, m \le 50$。

时间限制2s,空间限制2G。

题解

https://matthew99.blog.uoj.ac/blog/5352