Поиск k-ой в лексикографическом порядке скобочной последовательности

Материал из Algocode wiki
Версия от 18:04, 6 февраля 2021; Глеб (обсуждение | вклад)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Решение

Будем строить нашу последовательность слева направо, как в перестановках. Чтобы узнавать, сколько скобочных последовательностей мы скипнули, поставив ")" вместо "(" нам потребуется динамика, которая возвращает количество ПСП с заданным балансом и нужной длиной .



Автор конспекта: Александр Гришутин

По всем вопросам пишите в telegram @rationalex