网站页面
当前课程
成员
General
主题 1
主题 2
主题 4
主题 5
主题 6
主题 7
主题 8
主题 9
主题 10
主题 11
主题 12
主题 13
主题 14
主题 15
主题 16
主题 17
主题 18
主题 19
主题 20
背诵单词
成绩 | 0 | 开启时间 | 2013年02月21日 星期四 23:02 |
折扣 | 0.8 | 折扣时间 | 2013年02月28日 星期四 23:02 |
允许迟交 | 是 | 关闭时间 | 2013年02月28日 星期四 23:02 |
输入文件 | letter.in | 输出文件 | letter.out |
【问题描述】
小小在背单词,她发现当背诵了单词 beauty 以后 ,再接着背诵单词 beautiful 就会觉得容易许多。由于有很多单词要背,她希望找到一种好的背诵顺序。单词 A 和它的前驱 B 的最大公共前缀的长度称为背诵单词 A 的便利值 ( 例如: B= ' beauty ' ,A= ' beautiful ' , 则 A 的便利值是 len({A,B})=len( ' beaut ' )=5), 我们认为一个背诵单词 A 的花费是它的长度 ( 例如 : ' beautiful '的长度 len( ‘ beautiful ' )=9) 与它的便利值之差(对于上述例子背诵 A 的花费为 9-5=4 )。请你求一个背诵顺序,使得背诵这些单词的花费总和最小。假设一开始你什么单词都不记得。
【输入格式】
给定一个单词表:第一行 N ( N < 100 )表示单词总数。接下来 N 行,每行一个单词。每个单词的长度不超过 20 ,均为小写字母组成。
【输出格式】
按照背诵顺序输出每个单词,每个单词占一行,不能有多余的字符。(若有多组,输出字典序最小的一组)
【输入输出样例】
输入:
letter.in
5
beauty
beautiful
flower
man
dog
输出:
letter.out
beautiful
beauty
dog
flower
man