Two Subsequences

题意翻译

# CF83E 两个子序列 ### 题目描述 在一堂IT课上，Valera 学习了数据压缩。我们现在将向你介绍老师所讲解的一种新的数据压缩方法。 定义压缩函数 $f()$： - $f($空序列$)=$ 空字符串 - 对于任意一个字符串 $s$，$f(s)=s$。 - 对于任意两个字符串 $s_{1}$，$s_{2}$，$f(s1,s2)$ 为包含前缀 $s_{1}$ 且包含后缀 $s_{2}$ 的字符串中长度最小的一个。 - 对于任意 $n$ 个字符串，$f({s_{1},s_{2},\ldots,s_{n}})=f(f({s_{1},s_{2},\ldots,s_{n-1}}),s_{n})$ 例如： 1. $ f(001,011)=0011 $ 2. $ f(111,011)=111011 $ 2. $f(000,000,111)=f(f(000,000),111)=f(000,111)=000111 $ . 现在 Valera 面临一个难题：他需要将给定的需要压缩的序列 ${a_{1},a_{2},\ldots,a_{n}}$ 分成两个新的序列 ${b_{1},b_{2},\ldots,b_{k}}$ 和 ${c_{1},c_{2},\ldots,c_{m}}$ $(k+m=n)$ ，使得$S=|f({b_{1},b_{2},\ldots,b_{k}})|+|f({c_{1},c_{2},\ldots,c_{m}})|$ 的值最小。这里 $|p|$ 表示字符串 $p$ 的长度。 **注意**： 1. 不允许在子序列中更改元素的相对顺序。 2. 可以使得 $mk=0$ 即可以使得序列 $b$ $c$ 中的一个为空。 3. 对于原序列 $a$ 中的任意一项 $a_{i}$，不得既不存在于 $b$ 中，亦不存在于 $c$ 中。也不得同时存在于 $b$ 和 $c$ 中。 4. $b$ $c$ 中的元素在 $a$ 中不必连续，即 $b$ 和 $c$ 的元素可以在 $a$ 中交替出现(参见样例2、3)。 ### 输入格式 第一行一个整数 $n$，表示序列 $a$ 的项数。 接下来 $n$ 行，每行一个字符串，第 $i+1$ 行输入的字符串表示序列 $a$ 的第 $i$ 项，即 $a_{i}$。 输入数据保证序列 $a$ 中的所有项长度相同，并且仅由数字 $0$ 或 $1$ 组成。 ### 输出格式 一行一个整数，$S$ 的最小值。 ### 样例解释 1. 样例解释1 最佳的方法为：一个子序列为空，另一个子序列等于原始序列 $a$。此时$S_{min}=|f(01,10,01)|=|f(f(01,00),01)|=| f(010,01)|=|0101|=4$。故输出 $4$。 2. 最好的选择是：$b={000,001}$，$c={111,110}$。此时$S_{min}=|f（000,001）|+|f（111,110）|=|0001|+|1110|=8$。故输出 $8$。 3. 最好的选择是：$b={10101,01010,01000}，c={11111,10010}$。此时$S_{min}=(|10101000 |+|111110010 |=17$。故输出 $16$。 Translated by: @xhz0311

题目描述

On an IT lesson Valera studied data compression. The teacher told about a new method, which we shall now describe to you. Let $ {a_{1},a_{2},...,a_{n}} $ be the given sequence of lines needed to be compressed. Here and below we shall assume that all lines are of the same length and consist only of the digits $ 0 $ and $ 1 $ . Let's define the compression function: - $ f( $ empty sequence $ )= $ empty string - $ f(s)=s $ . - $ f(s_{1},s_{2})= $ the smallest in length string, which has one of the prefixes equal to $ s_{1} $ and one of the suffixes equal to $ s_{2} $ . For example, $ f(001,011)=0011 $ , $ f(111,011)=111011 $ . - $ f(a_{1},a_{2},...,a_{n})=f(f(a_{1},a_{2},a_{n-1}),a_{n}) $ . For example, $ f(000,000,111)=f(f(000,000),111)=f(000,111)=000111 $ . Valera faces a real challenge: he should divide the given sequence $ {a_{1},a_{2},...,a_{n}} $ into two subsequences $ {b_{1},b_{2},...,b_{k}} $ and $ {c_{1},c_{2},...,c_{m}} $ , $ m+k=n $ , so that the value of $ S=|f(b_{1},b_{2},...,b_{k})|+|f(c_{1},c_{2},...,c_{m})| $ took the minimum possible value. Here $ |p| $ denotes the length of the string $ p $ . Note that it is not allowed to change the relative order of lines in the subsequences. It is allowed to make one of the subsequences empty. Each string from the initial sequence should belong to exactly one subsequence. Elements of subsequences $ b $ and $ c $ don't have to be consecutive in the original sequence $ a $ , i. e. elements of $ b $ and $ c $ can alternate in $ a $ (see samples 2 and 3). Help Valera to find the minimum possible value of $ S $ .

输入输出格式

输入格式

The first line of input data contains an integer $ n $ — the number of strings ( $ 1<=n<=2·10^{5} $ ). Then on $ n $ lines follow elements of the sequence — strings whose lengths are from $ 1 $ to $ 20 $ characters, consisting only of digits $ 0 $ and $ 1 $ . The $ i+1 $ -th input line contains the $ i $ -th element of the sequence. Elements of the sequence are separated only by a newline. It is guaranteed that all lines have the same length.

输出格式

Print a single number — the minimum possible value of $ 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

说明

Detailed answers to the tests: - The best option is to make one of the subsequences empty, and the second one equal to the whole given sequence. $ |f(01,10,01)|=|f(f(01,10),01)|=|f(010,01)|=|0101|=4 $ . - The best option is: $ b={000,001},c={111,110}. $ $ S=|f(000,001)|+|f(111,110)|=|0001|+|1110|=8 $ . - The best option is: $ b={10101,01010,01000},c={11111,10010}. $ $ S=|10101000|+|111110010|=17 $ .