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

Материал из Algocode wiki
Перейти к: навигация, поиск
Строка 1: Строка 1:
 
= Решение =
 
= Решение =
Будем строить нашу последовательность слева направо, как в [[Поиск k-ой в лексикографическом порядке перестановки|перестановках]]. Чтобы узнавать, сколько скобочных последовательностей мы скипнули, поставив ")" вместо "(" можно использовать [[Количество ПСП с заданным балансом и нужной длиной]] .
+
Будем строить нашу последовательность слева направо, как в [[Поиск k-ой в лексикографическом порядке перестановки|перестановках]]. Чтобы узнавать, сколько скобочных последовательностей мы скипнули, поставив ")" вместо "(" нам потребуется[[Количество ПСП с заданным балансом и нужной длиной|динамика, которая возвращает количество ПСП с заданным балансом и нужной длиной]] .
  
 
{{Автор|Александр Гришутин|rationalex}}
 
{{Автор|Александр Гришутин|rationalex}}
  
 
[[Категория:Конспект]]
 
[[Категория:Конспект]]

Версия 18:03, 6 февраля 2021

Решение

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



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

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