Codeforces Round 494 (Div. 3) |
---|
Закончено |
Дан текст, состоящий из $$$n$$$ слов, разделённых пробелами. Между каждой парой соседних слов ровно один пробел. Перед первым словом и после последнего слова нет пробелов. Длина текста — это количество букв и пробелов в нём. $$$w_i$$$ обозначает $$$i$$$-е слово текста. Все слова состоят только из строчных букв латинского алфавита.
Определим отрезок слов $$$w[i..j]$$$ как последовательность слов $$$w_i, w_{i + 1}, \dots, w_j$$$. Два отрезка слов $$$w[i_1 .. j_1]$$$ и $$$w[i_2 .. j_2]$$$ считаются одинаковыми, если $$$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$$$) — количество слов в тексте.
Следующая строка содержит $$$n$$$ слов $$$w_1, w_2, \dots, w_n$$$, разделённых пробелами. Каждое слово состоит из строчных латинских букв.
Гарантируется, что длина текста не превосходит $$$10^5$$$.
Выведите одно целое число — минимальную длину текста после использования не более чем одной аббревиации.
6
to be or not to be
12
10
a ab a a b ab a a b c
13
6
aa bb aa aa bb bb
11
В первом примере можно получить текст "TB or not TB".
Во втором примере можно получить текст "a AAAB AAAB c".
В третьем примере можно получить текст "AB aa AB bb".
Название |
---|