Всем привет. Прошу совет относительно динамического программирования. Прочитал уже достаточно теории о том, что это и возможные примеры. Однако, как приступаю к практике, а именно фильтрую архив задач по тегу ДП, начинаю пробовать решить какую-то задачу — ступор. Смотрю разбор, и возникают два вопроса:
Как определить, что будет означать $$$dp_{ij}$$$ для определенных $$$i, j$$$ в контексте данной задачи? (т.е. грубо говоря, что именно мы будем хранить в массиве дп)
Как определить эти "волшебные" формулы переходов?
В качестве совета также подойдет любая ссылка на подходящую литературу.
Заранее спасибо.
Расскажу, как у меня это происходило на примере задачи. 1316E - Выбор команды
Так, в задаче надо посчитать какую-то непонятную фигню, при этом, наверное, я смогу добавить человека и ее пересчитать. Наверное, задача на динамику.
Ага, $$$p \leq 7$$$. Возможно, в этой динамике одним из параметров будет маска членов команды.
Теперь нужно как-то ограничить рассмотренных людей. Ну тут работает стандартный способ — перебирать последнего рассмотренного.
Круто! $$$dp_{i, mask}$$$ — рассмотрели первые $$$i$$$ людей, при этом в команду набрали людей на позиции, отмеченные в $$$mask$$$.
Ой, там еще болельщики есть. Надо с ними тоже что-то делать. МБ засунуть количество взятых болельщиков в состояние? Нет, много получится, надо что-то другое.
О, если зафиксирована команда, то болельщиков можно просто жадно набирать! Давайте тогда просто будем перебирать людей в порядке убывания их веса как болельщика, и давать возможность стать болельщиком, если команда болельщиков пока слишком маленькая. Вроде как норм план.
Теперь нужны формулы. Ну тут мы очевидно перебираем все маски и последнего человека. У него есть три возможности:
В простых задачах на динамику отсутствуют пункты 5-6, поэтому эта задача и стала div2E. Да и в целом задачи на динамику на масках считаются сложными, я просто привел пример того, как я придумываю динамику в задачах.
Общие советы — чтобы придумать состояние, можно смотреть, что именно тебе нужно в задаче, каких параметров не хватает, чтобы ее посчитать. Иногда ограничения задачи могут в этом помочь.
Чтобы придумать формулы достаточно посмотреть, откуда ты можешь прийти в твое состояние — либо рассмотрев возможности последнего человека, хода и так далее. Т.е. рассматриваешь самый крайний случай, и формула получается!
Абсолютно неинтуитивно, как сделать вложенные списки, да еще и так, чтобы нумерация внешнего не пропала.