ДП по поддеревьям: различия между версиями
Глеб (обсуждение | вклад) |
Глеб (обсуждение | вклад) |
||
Строка 5: | Строка 5: | ||
===Пример задачи=== | ===Пример задачи=== | ||
− | Пусть задано взвешенное дерево, с весами $w_{i, j}$, где $i$ и $j$ — вершины дерева, соединённые ребром. Необходимо составить | + | Пусть задано взвешенное дерево, с весами $w_{i, j}$, где $i$ и $j$ — вершины дерева, соединённые ребром. Пусть вес паросочетания - сумма весов, написанных на ребрах. Необходимо составить [[паросочетание]] максимального веса в этом дереве. |
===Решение=== | ===Решение=== |
Версия 16:40, 13 декабря 2019
Содержание
Идея
Идея Динамического программирования, что мы решаем большую задачу, разбивая ее на маленькие, логично, что тогда маленькими подзадачами будут поддеревья этой вершины
Пример задачи
Пусть задано взвешенное дерево, с весами $w_{i, j}$, где $i$ и $j$ — вершины дерева, соединённые ребром. Пусть вес паросочетания - сумма весов, написанных на ребрах. Необходимо составить паросочетание максимального веса в этом дереве.
Решение
Пусть $dp_{i, 0}$ - максимальное паросочетание в поддереве $i$-й вершины, если мы еще не брали ребро из $i$ вершины, $dp_{i, 1}$ — если взяли, тогда, как посчитать $dp_{i, 0}$ для вершины, $dp_{i, 0} = \sum\limits_{v \in sons(i)} max(dp_{v, 0}, dp_{v, 1})$, так как если мы не берем ребро из $i$ вершины вниз, то мы можем взять любой ответ для сыновей. $dp_{i, 0} = max_{j \ \in \ sons(i)} \sum\limits_{v \in sons(i), v != j} max(dp_{v, 0}, dp_{v, 1}) + w_{i, j} + dp_{j, 0}$, так как мы точно должны взять ребро из $i$ в какого-то сына, а вот для всех остальных вершин можем выбрать, что хотим
Код
Другие задачи
Автор конспекта: Глеб Лобанов
По всем вопросам пишите в telegram @glebodin