ACMP 560: различия между версиями
Перейти к навигации
Перейти к поиску
Ctrlalt (обсуждение | вклад) (Новая страница: «== Ссылка на задачу == * [http://acmp.ru/?main=task&id_task=560 ACMP #560 — Остановки] == Похожие задачи == * Инт…») |
Ctrlalt (обсуждение | вклад) Нет описания правки |
||
| Строка 15: | Строка 15: | ||
[[Category: Сборник задач: ACMP]] | [[Category: Сборник задач: ACMP]] | ||
[[Category: Задачи: Динамическое программирование — два параметра]] | [[Category: Задачи: Динамическое программирование — два параметра + привязка]] | ||
[[Category: Задачи: Дерево отрезков]] | [[Category: Задачи: Дерево отрезков]] | ||
Текущая версия от 23:56, 13 января 2015
Ссылка на задачу
Похожие задачи
Комментарии
Вид подзадачи: d[i][j] — минимальная стоимость постройки i остановок, если последняя из них заканчивается в клетке a[j].
Рекуррентная формула: d[i][j] = min(d[i - 1][k] + ∑a[t]), где k ∈ (j - l - R)..(j - l - r), t ∈ (j - l + 1)..j.
База рекурсии: Если j < r + l - 1, или i × (l + r) > j + 1, или i × (l + R) < j + 1, то d[i][j] = INF. Если s[1][j] ≠ INF, то d[1][j] = ∑a[t]; где t ∈ (j - l + 1)..j.
Вид ответа: min(d[n][k]), где k ∈ (L - R - 1)..(L - r - 1). Сложность O(N × L × R), с деревом отрезков — O(N × LlogL).