ДП по поддеревьям: различия между версиями

Материал из Algocode wiki
Перейти к: навигация, поиск
 
Строка 9: Строка 9:
 
===Решение===
 
===Решение===
  
Пусть $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, 1} = 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$ в какого-то сына, а вот для всех остальных вершин можем выбрать, что хотим
+
Пусть $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, 1} = 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$ в какого-то сына и для этого сына $x$ мы имеем право взять только $dp_{x, 0}$, а вот для всех остальных вершин можем выбрать, что хотим
  
 
===Другие задачи===
 
===Другие задачи===

Текущая версия на 20:41, 17 декабря 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, 1} = 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$ в какого-то сына и для этого сына $x$ мы имеем право взять только $dp_{x, 0}$, а вот для всех остальных вершин можем выбрать, что хотим

Другие задачи



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

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