689
правок
Изменения
м
→Общий алгоритм: минус жир
=== Общий алгоритм ===
Выполним Modify(), после чего разобъем все множество работ на блоки и для каждого блока запустим '''Decompose'''():
<tex> 1 \mid prec, pmtn, r_i \mid f_{max} </tex>()
1 Modify()
2 B = '''Blocks(<tex> \{1 \ldots n \} </tex>)
3 ans = - <tex> \infty </tex>
4 for (<tex> B_i \in </tex> B):
5 ans = <tex> \max </tex> (ans, '''Decompose'''(<tex> B_i </tex>))
6 return ans
== Время работы ==
Лемма: время работы алгоритма <tex> 1 \mid prec, pmtn, r_i \mid f_{max} </tex> — <tex> O(n^2) </tex> операций.
