Палиндром - это симметричная строка символов, то есть такая, которая одинаково читается слева направо и справа налево. Требуется составить программу PALINDR, которая дл язаданной строки определяет наименьшее количество символов, которые нужно вставить в эту строку чтоб получить палиндром. Например, строку "Ab3bd" можно превратить в палиндром путем вставки двух символов ("dAb3bAd" или "Adb3bdA") и меньшим количеством этого добится нельзя.
Входной файл PALINDR.IN содержит одну строку - исходную строку символов. Длина ее не превышает 5000.
Единственная строк выходного файла PALINDR.OUT должна содержать искомое минимальное количество символов.

Пример входных и выходных данных:
PALINDR.IN
Ab3bd

PALINDR.OUT
2

решение выкладывать?

ну, идею свою скажи. Вроде больше никому не интересно.

Ну например...

Выбираем один символ, считаем что он будет центральным. Если рядом сотят 2 одинаковых символа - считаем эту пару как один.
Движемся двумя курсорами - один вправо, второй влево. Считаем количество несоответствующих (и следовательно требующих добавления) символов, пока оба курсора не выйдут на границу слова. Приоритет - добавление с короткой стороны, однако реально надо обрабатывать все варианты.
Повторяем с каждым символом строки.
Печатаем минимальное из полученных.

просто решение (без оптимизации):
смотрим на слово (1,n):
1. крайние буквы совпадают - берем все, что между ними, и решаем задачу для подслова (2,n-1)
2. разные - надо добавить либо слева, либо справа, решаем задачу для (1,n-1) и (2,n), выбираем минимальное
пока чистая рекурсия
сложность - что-то вроде порядка экспоненциальной (2^n)
при небольших n можно на этом остановиться
если хочется ускорить, замечаем, что слово (2,n-1) будет обрабатываться два раза:
1. после (1,n-1)
2. после (2,n)
вот и место для оптимизации
дальше, кстати, идет стандартная методика, которую можно применить в куче задач:
предположим, у нас есть реккурентный поиск чего-то оптимального

1. переделываем рекурсию в цикл с использованием стека
2. переделываем стек в очередь (что соответствует замене поиска в глубину поиском в ширину)
3. начинаем отсеивать элементы при добавлении в очередь

в нашем случае это выглядит так:
1. делаем очередь из троек чисел: (начало подслова, конец подслова, значение критерия
2. ставим туда (1,n,0)
3. цикл
3.1. берем очередной элемент очереди
3.2. если буквы совпадают, добавляем в очередь (начало+1, конец-1, критерий - не изменился)
3.3. если буквы разные
3.3.1. добавляем в очередь (начало+1, конец, критерий+1)
3.3.2. добавляем в очередь (начало, конец-1, критерий+1)
4. когда остались только одиночные символы, выбираем тот, у которого меньше критерий

!!!пока сложность осталась экспоненциальной!!!

добавляем правило отсева:
процедура добавления элемента в очередь:
1. если элемента с такими началом и концом нет в очереди - просто добавляем
2. если есть - смотрим, какой критерий меньше, минимум записываем в этот элемент - остается опять один элемент с, возможно, уменьшившимся критерием

после этого сложность уже не превышает количества всевозможных пар (начало, конец) - N^2 (в смысле порядка)...

Это сообщение отредактировал(а) maxim1000 - 16.3.2005, 11:07