Восстановление k-го числа с особым свойством

Материал из Algocode wiki
Версия от 09:14, 20 марта 2020; Глеб (обсуждение | вклад) (Новая страница: «Недавно была тема восстановление $k$-ого комбинаторного объекта и там для восстановление...»)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Недавно была тема восстановление $k$-ого комбинаторного объекта и там для восстановление сложных объектов мы использовали динамику, значит восстановление $k$-ого числа наверное тоже можно делать через динамику, например пусть дана задача найти $k$ число с суммой цифр = $s$, первым делом нам надо найти длину такого числа, то есть найти $min(x), dp[x][s] >= k$, теперь нам нужно восстановить само число, для этого давайте переберем первую цифру от 1 до 9, найдем минимальную для которой возможно, затем переберем вторую цифру и так далее.



Автор конспекта: Глеб Лобанов

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