47
правок
Изменения
м
→Псевдокод
Заметим, что с помощью этого преобразования мы сократили общее время вычисления с <tex>O(n^2)</tex> до <tex>O(n)</tex>.
===ПсевдокодРеализация=== calculate(vertexv, useRoot): if dp[vertexv][useRoot] != -1: return dp[vertexv][useRoot] //вернули уже посчитанное значение dp[vertex][root]
sum = 0
if use_root == 0: //случай 1: не берем ребра из корня
for u in child(vertexдля)всех u из множества детей v:
sum += calculate(u, 1)
dp[vertexv][useRoot] = sum
return sum
max1 = dp[vertexv][0] for x in child(vertex): //случай 2: берем какое-то ребро for (для) всех x из множества детей v: max1 = max(max1, calculate(x, 0) + calculate(vertex, 0) - calculate(x, 1) + w[vertexv,x]) dp[vertexv][useRoot] = max1 return dp[vertexv][useRoot]
==Ссылки==
