Как сделать сокращение от самой длинной общей подпоследовательности к O (nlog n) Самая длинная нарастающая подпоследовательность для проблемы 10635 uva. Мне нужна помощь относительно логики, которая будет применяться для решения проблемы.Как использовать LIS для решения 10635 uva
Для каждого шага маршрута одного из двух символов (скажем, принцессы) назначьте номер этого шага в последовательности принца.
Первое наблюдение - все шаги, не входящие в последовательность принца, немедленно удаляются - они не могут быть частью общей последовательности ходов.
Теперь у нас есть последовательность чисел, представляющая индекс в последовательности ходов принца. Мы должны выбрать возрастающую подпоследовательность (увеличивающуюся, поскольку мы должны посещать ячейки в том же порядке, что и принц) максимальной длины этой последовательности. Звонок каких-нибудь колоколов?
Надеюсь, это поможет.
Буду благодарен, если вы дадите более точное и четкое определение того, что вы подразумеваете под «назначением числа этого шага в последовательности принца» в первой строке вашего ответа. – whitepearl
Путь каждого символа - это массив, в котором у вас есть ячейка, посещенная на данном шаге. Итак, вы имеете этот массив для принца, и вы проходите через клетки принцессы, и для каждой ячейки, присутствующей в массиве принца, вы назначаете индекс этой ячейки в массиве принца, вы уклоняетесь от клеток, которые не присутствуют в массив князя. Теперь вам нужно сделать LIS на числа, которые вы получили (т. Е. Indecies). Надеюсь, это станет более ясным. –
Если для каждого элемента массива принцессы мы находим соответствующий элемент в матрице принца, это становится алгоритмом O (nm). Что поражает цель использования O (nlog n) LIS для этого вопроса. Я понял, что вы упоминали в своем посте, и даже выполнил то же самое и получил TLE :(Исправьте меня, если я ошибаюсь в любом месте или существует какой-либо другой метод для решения вопроса. – whitepearl