Re: Строки
Можно динамикой попробовать:
Состояние: dp(i) - минимальное количество символов, которое надо удалить, чтобы покрыть префикс строки длины i словами из словаря.
База: dp(0) = 0
Переходы: для i пробовать каждое слово из словаря j - удалять с конца минимум символов, чтобы это слово можно было вставить (жадно идя с конца): dp(i) = min(dp(k) + i - k - word(j).length(), j = 0 .. word.size() - 1)
Что-то такое.
Сложность получится N^2 * M.
3 2011-12-27 22:14:01 Отредактировано Jumbo (2011-12-27 22:14:13)
Re: Строки
Сдал, вот код: http://www.ideone.com/njVld
Re: Строки
Сдал, вот код: http://www.ideone.com/njVld
Спасибо Jumbo!