ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1039. Юбилейная вечеринка

I found the reason for me WA on 13#
Послано fytain 25 июл 2013 09:50
my method is DP:
//invite
int sum = 0;
for (Integer c : guest.children) {
    sum += DP[c.intValue()][0];
}
DP[index][1] = sum + RATE[index];

// do not invite
sum = 0;
for (Integer c : guest.children) {
    int max = Math.max(DP[c.intValue()][0], DP[c.intValue()][1]);
    sum += max;
}
DP[index][0] = sum;



at first, I got WA on 13#,
DP the tree should from leaf to root,
but at first I sort the guests by its children count,
the right way is sort the guests by depth

Edited by author 25.07.2013 09:50