689
правок
Изменения
→Decompose: minor fixes
3 G <tex> \leftarrow </tex> Blocks(<tex> B \setminus l </tex>)
4 вставить l в промежутки между блоками G, начиная с <tex> r_l </tex>
5 '''for''' B_j <tex> B_j \in G </tex>:
6 ans = max(ans, Decompose(<tex> B_j </tex>))
7 return ans
Найдем теперь нижнюю оценку на <tex> f_{max} </tex>. Пусть <tex> f_{max}(J) </tex> — ответ для множества работ <tex> J </tex>.
Очевидно, для любой работы <tex> j \in J </tex> выполняется <tex> f_{max}(J) \ge f_{max}(J \ setminus j) </tex>, значит, <tex> f_{max}(J) \ge \max\limits_{j \in J} f_{max}(J \ setminus j) </tex>.
Также, так как в оптимальном решении какая-то работа без потомков обязательно заканчивается в блоке <tex> B </tex>, то <tex> f_{max}(J) \ge f_l(e) </tex>.
Отсюда следует <tex> f_{max}(J) \ge \max(f_l(e), \max\limits_{j \in J} f_{max}(J \ setminus j)) </tex>. По псевдокоду алгоритма видно, что его ответ достигает этой нижней оценки.
}}
