ACMP 560
(перенаправлено с «Интернет-олимпиада 12.11.2005, усложнённый уровень, F»)
Перейти к навигации
Перейти к поиску
Ссылка на задачу
Похожие задачи
Комментарии
Вид подзадачи: 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).