Редактирование: Pintreepi1Lmax

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

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 52: Строка 52:
 
     '''if''' q[t] == m
 
     '''if''' q[t] == m
 
       F = t + 1
 
       F = t + 1
     '''int''' j = child[i]
+
     '''Job''' j = i.child
 
     r[j] = max(r[j], t + 1)
 
     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>d_{k}</tex>, и, следовательно, <tex>L_{k}</tex> не поменяются.
+
В результате ответ можно получить, зная конечный массив <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> не поменяются в соответствии с алгоритмом)
  
 
=== Доказательство корректности ===
 
=== Доказательство корректности ===

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)