Получение номера по ПСП: различия между версиями
Материал из Algocode wiki
Глеб (обсуждение | вклад) (Новая страница: «=Задача= Дана ПСП, требуется получить ее номер в лексикографическом порядке =Идея= Замет...») |
Глеб (обсуждение | вклад) |
||
Строка 8: | Строка 8: | ||
=Решение= | =Решение= | ||
− | Номер | + | Номер ПСП = $\sum \limits_{i} amount(n - i - 1, bal + 1) \cdot (a[i] == ')')$ |
{{Автор|Глеб Лобанов|glebodin}} | {{Автор|Глеб Лобанов|glebodin}} | ||
[[Категория:Конспект]] | [[Категория:Конспект]] |
Текущая версия на 15:07, 6 февраля 2021
Задача
Дана ПСП, требуется получить ее номер в лексикографическом порядке
Идея
Заметим, что также как и в Получение номера по перестановке для каждой позиции нас интересует только то сколько меньших лексикографически вариантов могло стоять на этой позиции, так как любой вариант меньше на этой позиции дает меньшие ПСП независимо от суффикса, следовательно давайте для каждой позиции посчитаем сумму сколько вариантов меньше из-за того, что число на этой позиции меньше, а это мы умеем делать с помощью Динамики из пункта выше.
Решение
Номер ПСП = $\sum \limits_{i} amount(n - i - 1, bal + 1) \cdot (a[i] == ')')$
Автор конспекта: Глеб Лобанов
По всем вопросам пишите в telegram @glebodin