Codeforces Round 741 (Div. 2) |
---|
Закончено |
Rise above the sands of time...
Преодолев, наконец, Подветренные Пустоши, Ори добрался до Развалин Ветров, дабы отыскать Сердце Леса! Однако древнее хранилище, содержащее этот бесценный свет Ивы, не желало открываться!
Ори очень этому удивился, но огонек объяснил ему: хитрые Горлеки решили наложить дополнительную защиту на хранилище.
Горлеки очень любили операцию «разворачивания строки». А еще они очень любили возрастающие подпоследовательности.
Пусть дана строка $$$s_1s_2s_3 \ldots s_n$$$. Тогда «разворачиванием» этой строки назовем последовательность строк $$$s_1$$$, $$$s_1 s_2$$$, ..., $$$s_1 s_2 \ldots s_n$$$, $$$s_2$$$, $$$s_2 s_3$$$, ..., $$$s_2 s_3 \ldots s_n$$$, $$$s_3$$$, $$$s_3 s_4$$$, ..., $$$s_{n-1} s_n$$$, $$$s_n$$$. Например, «разворачиванием» строки 'abcd' будет последовательность строк 'a', 'ab', 'abc', 'abcd', 'b', 'bc', 'bcd', 'c', 'cd', 'd'.
Чтобы открыть древнее хранилище, Ори должен найти длину наибольшей возрастающей подпоследовательности «разворачивания» строки $$$s$$$. Здесь строки сравниваются лексикографически.
Помогите Ори справиться с этой задачей!
Строка $$$a$$$ лексикографически меньше строки $$$b$$$, если и только если выполняется один из следующих пунктов:
Каждый тест содержит несколько наборов входных данных.
В первой строке находится одно целое положительное число $$$t$$$ ($$$1 \le t \le 10^3$$$) — количество наборов входных данных. Описание наборов входных данных приведено ниже.
В первой строке каждого набора входных данных находится одно целое положительное число $$$n$$$ ($$$1 \le n \le 5000$$$) — длина строки.
Во второй строке каждого набора входных данных находится непустая строка длины $$$n$$$, состоящая из строчных латинских букв.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$10^4$$$.
Для каждого набора входных данных выведите в отдельной строке одно целое число — ответ на задачу.
7 5 acbac 8 acabacba 12 aaaaaaaaaaaa 10 abacabadac 8 dcbaabcd 3 cba 6 sparky
9 17 12 29 14 3 9
В первом наборе входных данных «разворачивание» строки выглядит так: 'a', 'ac', 'acb', 'acba', 'acbac', 'c', 'cb', 'cba', 'cbac', 'b', 'ba', 'bac', 'a', 'ac', 'c'. В качестве наибольшей возрастающей подпоследовательности можно выбрать, например, 'a', 'ac', 'acb', 'acba', 'acbac', 'b', 'ba', 'bac', 'c'.
Название |
---|