317
правок
Изменения
→Второй шаг
F = 0
'''for''' '''int''' i = 1 .. n
r[i] = 0
'''for''' '''int''' t = 0 .. n
q[t] = 0
'''for''' '''int''' i = 1 .. n '''int''' t = max(r[i], F)
x[i] = t
q[t] = q[t] + 1
j = i.child()
r[j] = max(r[j], t + 1)
В результате ответ можно получить, зная конечный массив <tex>\mathtt x</tex> и делайны работ: <tex>L_{max} = \max\limits_i \{\mathtt x[i] - \mathtt j[i].deadline\}</tex>, где <tex> \mathtt j</tex> {{---}} массив работ. Можно заметить, что при вычислении ответа неважно, какие дедлайны использовать, начальные или релаксированные, потому что для любого <tex>k</tex> и его предка <tex>i</tex> выполняется неравенство <tex> \mathtt j[k].deadline \leqslant \mathtt j[i].deadline - 1</tex>, а значит, после релаксации минимум не изменится. (При условии, что существует правильное расписание)
=== Доказательство корректности ===
