Блог пользователя caustique

Автор caustique, 13 лет назад, По-русски

Подскажите, где можно прочитать про методы решения задач на динамику на дереве ну и порешать эти задачи. А то оранжевый цвет получил, а эту тему до сих пор не осилил, что обидно.

  • Проголосовать: нравится
  • +9
  • Проголосовать: не нравится

13 лет назад, # |
Rev. 2   Проголосовать: нравится +2 Проголосовать: не нравится

Если подразумевается ДП на деревьях - то возможно стоит попробовать решить относительно простую для оранжевых  задачу "Двоичная яблоня" с Тимуса.

Успехов!

13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
Обычно дерево ориентируют из какой-нибудь нужной нам вершины. Далее делают топологическую сортировку и собирают ответ "снизу-вверх". В вершине храним результат для всего поддерева из этой вершины. Топсорт можно и не делать, а считать все прямо в dfs'е "сверху-вниз".
Вот 4 задачи, которые хорошо мне помогли разобраться:
http://acm.timus.ru/problem.aspx?space=1&num=1362
http://acm.timus.ru/problem.aspx?space=1&num=1371
http://acm.timus.ru/problem.aspx?space=1&num=1389
http://acm.timus.ru/problem.aspx?space=1&num=1039
13 лет назад, # |
  Проголосовать: нравится -14 Проголосовать: не нравится
Оранжевый как получил так и просрал.
Можешь её вообще не учить.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Задачка из той же серии, решайте на здоровье!
http://acmp.ru/index.asp?main=task&id_task=212
»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

а где можно прочитать о Динамике по дереву(теоретический материал)?

»
12 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Не знаю подходит ли, но интересно http://codeforces.com/blog/entry/337

»
12 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

http://codeforces.com/gym/100030 задача І отсюда, но ее вроде можно и без дп. http://codeforces.com/contest/161/problem/D