tgoop.com/sbornik_olprog/246
Last Update:
Бывают игры, которые можно представить в виде графа, в котором каждая вершина соответствует состоянию игры, а ребра - переходами между этими состояниями. Причем, часто такой граф ациклический (DAG)
Каждую вершину в таком графе можно считать выигрышной или проигрышной, в зависимости от того выигрывает или проигрывает игрок, начиная в таком состоянии. ВАЖНО: это верно именно для DAG! В произвольных графах могут быть еще и ничейные вершины
Таким образом, такие задачи сводятся к подсчету DP на DAG. То есть либо заранее понятно как перебирать вершины, либо надо делать топсорт
Пререквизиты:
🔙 ДП, ДП на поддеревьях
🔙 DFS, Топсорт
Еще теория + первая задача:
📚 Материал от Яндекс Кружка - теория + примеры задач (жаль картинки пропали😢)
📚 Emaxx - небольшая теория с кодом конкретной задачи (большеват правда)
💻 Задача с Тимуса 1 - БАЗА 1. Сразу граф задан
💻 Задача с Тимуса 2 - БАЗА 2. Сразу граф задан
💻 Задача с Тимуса 3 - Уже самим перебирать надо, но в лоб
💻 Задача с Тимуса 4 - Уже надо придумать
Контест и ответы на частые вопросы в посте автора
Теги: #алгоритмы #игры #контест #ДП
Автор: https://www.tgoop.com/KogutIvanTutoring
BY Сборник Олпрогера
Share with your friend now:
tgoop.com/sbornik_olprog/246