192
правки
Изменения
м
→Алгоритм
==Алгоритм==
Отсортировать работы так, чтобы <tex>f_i</tex> удовлетворяла условиям неубывания;
for s, e <tex>\in</tex> T : s <tex>\leq</tex> e
<tex>F_0</tex>(s, e) = 0;
for k = 1..n
for s, e <tex>\in</tex> T : s <tex>\leq</tex> e
if <tex>r_k</tex> <tex>\notin</tex> [s - p, e)
<tex>F_k</tex>(s,e) = <tex>F_{k-1}</tex>(s,e)
else
<tex>F'_k</tex>(s,e) = <tex>F'</tex>(s,e), где
<tex>F'_k</tex>(s,e) = min{<tex>F_{k-1}</tex>(s,t_k) + <tex>F_{k-1}</tex>(t_k + p, e) + <tex>f_k</tex>(t_k + p)| <tex>t_k</tex> <tex>\in</tex> T; max{s, <tex>r_k</tex>} <tex>\leq</tex> <tex>t_k</tex> <tex>\leq</tex> e - p};
return <tex>F_n($$\min_{i=1}^{n}r_i$$, max_{t \in T}t + p)</tex>
==Время работы==
