|
|
|
|
|
|
|
Вернуться
| 1 Ишмаметьев Иван Анатольевич, 21 сентября 2012 г. 13:52:32 | |
|
Ларичев, спасибо большое! Жаль за третье никто не взялся.
|
|
|
| 2 Ларичев, 20 сентября 2012 г. 13:16:32 | |
Задача 4.
Условие:
Нам дан связный граф с n вершинами (n - 1) ребром, то есть дерево. Мы можем красить каждую из вершин в любой из тех цветов, в который разрешил нам красить её Сева. Таких цветов до 3. При этом вершины, которые соединены ребром, должны быть разных цветов. Максимизировать число вершин цвета “индиго”, следуя данным правилам.
Решение:
Будем решать эту задачу методом динамического программирования, а конкретно – динамикой на поддеревьях.
Заведем массив dp[MAXN][3], в котором dp[i][j] будет означать – можно ли сделать так, чтобы поддерево вершины i было корректным если i-тая вершина будет цвета j, а если можно, то максимальное число “индиго” в поддереве, включая i-тую.
Подвесить дерево можно как угодно, поэтому проще всего просто запустить dfs(0). Так как граф связный, то этот проход обойдёт все вершины и будет ничем не хуже других.
Теперь сам dfs():
Вершина может быть 2-х типов:
1) Лист. Тогда мы говорим, что для данной вершины возможны все покраски, которые даны в условии, так как её поддерево – это она сама. Соответственно, dp[i][“индиго”] = 1, остальные цвета = 0, если конечно можно поставить.
2) Не лист. Мы должны предварительно посчитать динамику сначала для всех сыновей, запустив dfs() из них, чтобы потом это использовать. Затем по очереди пытаемся “вкручивать” разные лампочки (если можно конечно). Цвета сыновей должны отличаться от цвета нашей вершины. Если наша вершина, допустим, цвета “V”, то все сыновья должны быть цветов либо “I”, либо “U”. И из таких вариантов выбрать тот, у которого dp максимально и прибавить к нашему текущему dp[i][j] (Если j = “индиго”, то еще +1). Если мы не можем поставить данный цвет j с учётом всех правил, то как-то помечаем dp[i][j] – некорректно. (Например можно присваивать -2e9, чтобы меньше if-ов писать) .
Ответ:
Ответом будет max(max(dp[0][0], dp[0][1]), dp[0][2]).
|
|
|
| 3 Беляев Сергей Николаевич, 20 сентября 2012 г. 3:54:21 | |
|
Нет, по крайней мере с моей стороны. Но всегда могут найтись желающие и сделать это, например, в данной теме. Такое уже бывало.
|
|
|
Чтобы оставить сообщение необходимо зарегистрироваться и авторизоваться!
| | | |
