Задана строка, символы которой могут повторяться. Нужно удалить все символы строки с помощью наименьшего количества вычеркиваний - C++ - Ответ 5905747

Пример. Вход: 1343223; выход: 4.

Анализ задачи. В строке 1343223 из примера можно вычеркнуть 22 (получится

13433), затем 1 и 4, а затем сразу три символа 3, т.е. всего четыре вычеркивания.

Предварительно "сожмем" слово, заменив каждую последовательность одинако-

вых символов, идущих подряд, одним таким символом, например, из 111223114

получим 12314. Очевидно, что ответ от этого не изменится, как и время работы в

худшем случае. Однако в среднем выигрыш будет существенным за счет уменьшения

числа подзадач (сложность "сжатия" линейна и не влияет на общую оценку — см

задачу 5.4). Кроме того, "сжатие" гарантирует, что все соседние символы различны.

Пусть а [1] …а [т] — строка, т — ее длина. Часть строки a [i] …а [ j ], состоя-

щую из всех символов с i’-го по j-Vi включительно, будем называть i…/-подстрокой

Серия подзадач очевидна: За какое минимально возможное количество вычеркивании

можно удалить u.j-подстроку? Нужная задача будет одной из задач серии, а именно

задачей размером (1, т).

Тривиальные подзадачи, решение которых очевидно — это подзадачи вида (i, i

(одиночный символ удаляется за один ход) и вида (i, i+1) (двухсимвольные подстро-

ки, состоящие из разных символов, удаляются за два хода).

Обозначим минимальное количество действий для удаления {..у-подстроки

через Тц. Оптимальным решением нетривиальной (1,у)-подзадйчи может быть такое:

перебрать все к, удовлетворяющие i
подстроку.

Таким образом, при a\i] *а [ j ] окончательный оптимум (/,./)-подзадачи достаточ-

но искать как ТҐ= Kv (согласно (13.14)), а при a [i] = а [j] следует рассмотреть Ку

и ЛГ* и выбрать из них меньшее.

Но и этого мало. Если одинаковые крайние символы «’…/-подстроки повторяются

внутри нее, то может оказаться, что выгоднее всего сначала удалить все подстроки,

разделяющие эти вхождения, а затем зачеркнуть все эти символы за один ход

(например, слово 1213141 лучше всего обработать, вычеркнув 2, 3, 4, а затем все

единицы за один ход).

Однако "может оказаться" не означает "непременно окажется". Рассмотрим слово

1231413215161. Любое его оптимальное решение (например, сначала вычеркнуть 4,

затем новообразуемые подстроки 11, 33, 22, затем 5, б, и, наконец, оставшиеся 1111)

требует удалять вторую и третью справа единицы (в позициях 9 и 11) вместе с крайними

(в позициях 1 и 13), а единицы в позициях 4 и 6 должны быть вычеркнуты раньше. Таким

образом, на последний ход нужно оставить много единиц, но не все.

Может показаться, что для реализации этой идеи нужен полный перебор под-

множеств вхождений символов, одинаковых с a [i] и а [ j ]. Однако это не так бла-

годаря следующей идее.

Пусть для некоторой /../’-подстроки крайние символы a[i], a[j] совпадают

с некоторым внутренним а [к]. Тогда удаление сначала i+l..fc-1-подстроки, затем

k+\..j-\ – подстроки, затем трех одинаковых символов a[i]a[k]a[j] можно услов-

но свести к тому, что удаляется /..^-подстрока (но символ а [к] при этом загадочным

образом остается), а затем Ј. ../-подстрока. Из суммы количеств ходов по удалению

этих подстрок вычитается 1, поскольку при вычислении Т^+Т^ вычеркивание симво-

ла а [к] считается дважды:

Очевидно, что формула (13.16) позволяет собирать под одно вычеркивание много

одинаковых символов (если оптимальное решение хотя бы одной из (/,&)- и (k,j)-

подзадач получено по этой же формуле), не требуя, чтобы все одинаковые символы

вычеркивались обязательно за один раз.

Как и в задачах об умножении матриц и о максимальном значении выражения,

формулы (13.14)—(13.17) следует реализовать либо с помощью рекурсии с запомина-

нием, либо итеративно заполнить таблицу для 7^, двигаясь от главной диагонали по

линиям, параллельным ей, пока не придем в угловой элемент Т1т.

Вспомогательные величины Ку, K’tj и используются только для вычисления

Ту (при тех же i иу) и в дальнейшем их помнить не обязательно. Однако, реализуя

алгоритм с помощью рекурсии с запоминанием, эти вспомогательные значения все-

таки придется хранить (в массивах или в программном стеке). Так что преимущества

итеративного заполнения таблицы проявляются в данной задаче несколько ярче

чем в предыдущих.