Просмотр кода страницы ACMP 560

== Ссылка на задачу ==
* [http://acmp.ru/?main=task&id_task=560 ACMP #560 &mdash; Остановки]

== Похожие задачи ==
* [[Интернет-олимпиада 12.11.2005, усложнённый уровень, F]]

== Комментарии ==
Вид подзадачи: d[i][j] &mdash; минимальная стоимость постройки i остановок, если последняя из них заканчивается в клетке a[j]. 

Рекуррентная формула: d[i][j] = min(d[i - 1][k] + &sum;a[t]), где k &isin; (j - l - R)..(j - l - r), t &isin; (j - l + 1)..j.

База рекурсии: Если j < r + l - 1, или i &times; (l + r) > j + 1, или i &times; (l + R) < j + 1, то d[i][j] = INF.  Если s[1][j] &ne; INF, то d[1][j] = &sum;a[t]; где t &isin; (j - l + 1)..j.

Вид ответа: min(d[n][k]), где k &isin; (L - R - 1)..(L - r - 1). Сложность O(N &times; L &times; R), с деревом отрезков &mdash; O(N &times; LlogL).

[[Category: Сборник задач: ACMP]]
[[Category: Задачи: Динамическое программирование &mdash; два параметра + привязка]]
[[Category: Задачи: Дерево отрезков]]