← 返回题目列表

Codeforces · 1003/F

F. 缩写

中文机器翻译题面 查看原题

给您一个由 $$$n$$$ 空格分隔的单词组成的文本。任何一对相邻单词之间恰好有一个空格字符。第一个单词之前没有空格,最后一个单词之后也没有空格。文本的长度是其中字母和空格的数量。 $$$w_i$$$ 是文本中的第 $$$i$$$ 个单词。所有单词仅由小写拉丁字母组成。

让我们将一段单词 $$$w[i..j]$$$ 表示为单词序列 $$$w_i, w_{i + 1}, \dots, w_j$$$。如果 $$$j_1 - i_1 = j_2 - i_2$$$、$$$j_1 \ge i_1$$$、$$$j_2 \ge i_2$$$,并且对于每个 $$$t \in [0, j_1 - i_1]$$$$$$w_{i_1 + t} = w_{i_2 + t}$$$。例如,对于文本“to be or not to be”,段 $$$w[1..2]$$$ 和 $$$w[5..6]$$$ 是相等的,它们对应于单词“to be”。

缩写是用第一个大写字母替换某些单词片段。为了执行缩写,您必须选择至少两个不相交的相等单词段,并将每个选定的段替换为由该段中单词的首字母组成的字符串(以大写形式书写)。例如,对于文本“a ab a a b ab a a b c”,您可以将单词 $$$w[2..4]$$$ 和 $$$w[6..8]$$$ 的片段替换为缩写“AAA”,并获得文本“a AAA b AAA b c”,或者您可以将单词 $$$w[2..5]$$$ 和 $$$w[6..9]$$$ 的片段替换为缩写“AAAB”并获得文本“a AAAB AAAB c”。

最多一个缩写后的文本的最小长度是多少?

输入

输入的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 300$$$) — 文本中的单词数。

下一行包含文本 $$$w_1, w_2, \dots, w_n$$$ 中以空格分隔的单词。每个单词仅由小写拉丁字母组成。

保证文本长度不超过$$$10^5$$$。

输出

打印一个整数 — 最多一个缩写后的文本的最小长度。

示例

输入 #1

6
to be or not to be

输出 #1

12

输入 #2

10
a ab a a b ab a a b c

输出 #2

13

输入 #3

6
aa bb aa aa bb bb

输出 #3

11

注意

在第一个示例中,您可以获得文本“TB or not TB”。

在第二个示例中,您可以获得文本“a AAAB AAAB c”。

在第三个示例中,您可以获得文本“AB aa AB bb”。