ACMP 560

Ссылка на задачу

• 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).