← 返回题目列表

Codeforces · 83/E

E. 两个子序列

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

Valera 在 IT 课程中研究了数据压缩。老师讲了一个新方法,我们现在给大家介绍一下。

令 {a1, a2, ..., an} 为需要压缩的给定行序列。在这里和下面,我们假设所有行都具有相同的长度,并且仅包含数字 0 和 1。让我们定义压缩函数:

- f(空序列) = 空字符串
- f(s) = s。
- f(s1, s2) =  长度最小的字符串,其前缀之一等于 s1,后缀之一等于 s2。例如,f(001, 011) = 0011,f(111, 011) = 111011。
- f(a1, a2, ..., an) = f(f(a1, a2, an - 1), an)。例如,f(000, 000, 111) = f(f(000, 000), 111) = f(000, 111) = 000111。

Valera面临一个真正的挑战:他应该将给定的序列{a1, a2, ..., an}分成两个子序列{b1, b2, ..., bk}和{c1, c2, ..., cm},m + k = n,使得S的值 = |f(b1, b2, ..., bk)| + |f(c1, c2, ..., 厘米)|取尽可能小的值。这里|p|表示字符串p的长度。

请注意,不允许更改子序列中行的相对顺序。允许使子序列之一为空。初始序列中的每个字符串都应该恰好属于一个子序列。子序列 b 和 c 的元素不必在原始序列 a、i 中连续。 e. b 和 c 的元素可以在 a 中交替出现(参见示例 2 和 3)。

帮助 Valera 找到 S 的最小可能值。

输入

输入数据的第一行包含一个整数 n — 字符串的数量 (1 ≤ n ≤ 2·105)。然后在 n 行上跟随序列的元素 - 长度为 1 到 20 个字符的字符串,仅包含数字 0 和 1。第 i + 1 个输入行包含序列的第 i 个元素。序列的元素仅由换行符分隔。保证所有线的长度相同。

输出

打印一个数字——S 的最小可能值。

示例

输入 #1

3
01
10
01

输出 #1

4

输入 #2

4
000
111
110
001

输出 #2

8

输入 #3

5
10101
01010
11111
01000
10010

输出 #3

17

注意

测试详细答案:

- 最好的选择是将其中一个子序列设为空,第二个子序列等于整个给定序列。 |f(01, 10, 01)| = |f(f(01, 10), 01)| = |f(010, 01)| = |0101| = 4。
- 最佳选项是:b = {000, 001}, c = {111, 110}。 S = |f(000, 001)| + |f(111, 110)| = |0001| + |1110| = 8。
- 最佳选项是:b = {10101, 01010, 01000}, c = {11111, 10010}。 S = |10101000| + |111110010| = 17。