Вы не вошли. Пожалуйста, войдите или зарегистрируйтесь.
MAXimal :: φορυμ » Algo » Динамика по деревьям
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
Подскажите как решать такую задачу:
Дано дерево, для каждой вершины известно в какой из трёх цветов её можно покрасить, не разрешается смежные вершины красить в один цвет.
Нужно найти максимально возможное количество вершин первого цвета среди всех возможных раскрасок.
Спасибо.
Почему нельзя сделать такую простую динамику: d[v][c] - ответ для поддерева с корнем в v, если саму вершину мы покрасили в c (c=0..2).
Считается она так: пусть мы хотим посчитать ответ d[v][c]. Тогда каждый сын вершины v должен иметь цвет, отличный от c. Поскольку разные сыновья не влияют друг на друга, то можно просто для каждого сына to посмотреть значения динамик d[to][(c+1)%3] и d[to][(c+2)%3] и выбрать из них максимальное. Просуммировав это по всем сыновьям, и прибавив единицу, если c=0, мы получим искомое d[v][c].
Спасибо 
, сдал с такой идеей, но повозился с тем, что если мы, считая d[v][c], даже не попытались его обновить, то d[v][с]=-inf, а если, считая все d[v][0..2], не попытались обновить хотя бы один, то решения не существует)
И ещё с тем, что ответ - это максимум из d[root][0..2] после всего обхода, так как некоторые значения могут превратиться в -inf по пути)
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
MAXimal :: φορυμ » Algo » Динамика по деревьям