Как использовать ЛИС для решения 10635 УВА

Question

Как использовать ЛИС для решения 10635 УВА

Как выполнить сокращение от самой длинной общей подпоследовательности до O(nlog n) самой длинной возрастающей подпоследовательности для задачи 10635 uva. Мне нужна помощь относительно логики, которая будет применяться для решения проблемы.

2

algorithm lcs

Источник

user1288082 23 май '12 в 16:05

1 ответ

Другие вопросы по тегам algorithm lcs

user812912 23 май '12 в 16:14 2012-05-23 16:14 · Answer 1 · 2012-05-23 16:14

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

Первое наблюдение - все шаги, не присутствующие в последовательности принца, немедленно удаляются - они не могут быть частью общей последовательности ходов.

Теперь у нас есть последовательность чисел, представляющих индекс в последовательности ходов принца. Мы должны выбрать возрастающую подпоследовательность (увеличивающуюся, потому что мы должны посещать клетки в том же порядке, что и принц) максимальной длины этой последовательности. Звонит ли колокол?

Надеюсь это поможет.