1061. 文字栈

单点时限: 2.0 sec

内存限制: 256 MB

作为一个小镇报纸的编辑,你坚定的知道你的读者喜欢你每天发布的文字游戏,但是,你已经对那些文字游戏累了,并想要进行一个新的游戏。
给定一个 N 个文字的集合,找到一个排列,使得在单词前加入适当的空格后,使得每个单词和上一行单词重叠的部分的总数量最大。你的分数就是找到那个最大的值。

输入格式

输入数据包含一组或多组数据。
每组数据的第一行是一个整数 N(1<=N<=10), 表示有多少个单词在这个数据中。接下去的 N 行包含单词,每行一个。每个单词是由 ‘a’ 到 ‘z’ 的字母组成,长度在 1-10 之间 (包含 10).

当 N=0 时,输入结束。

输出格式

对于每组数据,你的程序应该输出一行,包含一个整数,表示符合游戏的最大值。
(Hint

Note: One possible arrangement yielding this score is:

aaa

abc

_bcd

__cde

bfcde

其中 ‘_’ 表示空格

)

样例

Input
5
abc
bcd
cde
aaa
bfcde
0
Output
8

13 人解决,34 人已尝试。

25 份提交通过,共有 109 份提交。

6.9 EMB 奖励。

创建: 18 年,6 月前.

修改: 7 年,3 月前.

最后提交: 1 年,5 月前.

来源: N/A

题目标签