Задача №111145. Две подпоследовательности
На уроке информатики Валерий изучал сжатие данных. Учитель рассказал новый метод, который мы сейчас вам опишем.
Пусть {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.
Перед Валерой стоит серьезная задача — разделить данную последовательность {a1, a2, ..., an} на две подпоследовательности {b1, b2, ..., bk} и {c1, c2, ..., cm}, m + k = n, так, чтобы величина S = |f(b1, b2, ..., bk)| + |f(c1, c2, ..., cm)| приняла минимально возможное значение. Здесь |p| обозначает длину строки p.
Обратите внимание, что запрещается менять относительный порядок строк в подпоследовательностях. Разрешается делать одну из подпоследовательностей пустой. Каждый элемент исходной последовательности должен принадлежать ровно одной из получившихся подпоследовательностей. Элементы подпоследовательностей b и c не обязательно должны идти подряд в исходной последовательности a, то есть они могут чередоваться (смотрите примеры 2 и 3).
Помогите Валере найти минимальное возможное значение S.
В первой строке входных данных содержится целое число n — количество строк (1 ≤ n ≤ 2·105). Далее в n строках даны элементы последовательности — строки длиной от 1 до 20 символов, состоящие только из символов 0 и 1. На i + 1 строке входных данных находится i-ый член последовательности. Элементы последовательности разделены исключительно символом перевода строки. Гарантируется, что все строки имеют одинаковую длину.
Выведите единственное число — минимально возможное значение S.
3
01
10
01
4
4
000
111
110
001
8
5
10101
01010
11111
01000
10010
17
Подробные ответы к тестам:
- Оптимальный вариант: сделать одну из подпоследовательностей пустой, а вторую — равной всей данной последовательности. S = |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.
Подзадача 1. N ≤ 10. Решение оценивается в 30 баллов.
Подзадача 2. N ≤ 1 000. Решение оценивается в 30 баллов.
Подзадача 3. Дополнительные ограничения отсутствуют. Решение оценивается в 40 баллов.
Подзадачи являются вложенными, т.е. баллы за подзадачу ставятся только при прохождении всех меньших подзадач.