Изменения

Перейти к: навигация, поиск

Pintreepi1Lmax

127 байт убрано, 22:52, 30 мая 2016
Второй шаг
'''if''' q[t] == m
F = t + 1
'''Jobint''' j = child[i.child]
r[j] = max(r[j], t + 1)
В результате ответ можно получить, зная конечный массив <tex>\mathtt x</tex> и делайны работ: <tex>L_{max} = \max\limits_i (\mathtt x[i] + 1 - d_{i}</tex>), так как все работы выполняются единицу времени, следовательно, <tex>C_{i} = \mathtt x[i] + 1</tex>. Можно заметить, что при вычислении ответа неважно, какие дедлайны использовать, начальные или релаксированные, потому что для любого <tex>k</tex> и его предка <tex>i</tex> либо производится релаксация и выполняется равенство <tex> d_{k} = d_{i} - 1</tex>, а значит, после релаксации максимум не изменится, поскольку при замене дедлайна на меньший максимум увеличится, а новое значение <tex>L_{k}</tex> будет равно <tex>L_{i}</tex>. (При условии, что существует правильное расписание. Если изначально было опоздание в вершине <tex>k</tex>либо мы не делали релаксацию, то и значение <tex>d_{k}</tex>, и, следовательно, <tex>L_{k}</tex> не поменяются в соответствии с алгоритмом).
=== Доказательство корректности ===
317
правок

Навигация