ACMP 661

Материал из Олимпиадное программирование в УлГТУ
Версия от 22:29, 13 января 2015; Ctrlalt (обсуждение | вклад) (Новая страница: «== Ссылка на задачу == * [http://acmp.ru/?main=task&id_task=661 ACMP #661 — «Стабильный» интернет] == Комментар…»)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)
Перейти к навигации Перейти к поиску

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

Комментарии

Если бы ограничения позволяли определить таблицу или один ряд:

Вид подзадачи: d[i][j] — минимальная стоимость стабильного интернета на интервале B..i, если использованы карты 1..j (карты упорядочены по времени).
Рекуррентная формула: d[k][j] = min(d[k][j], d[Bj][j - 1] + Sj), где k ∈ Bj..Ej.
База рекурсии: Если i <= l, то d[i][0] = 0, иначе d[i][0] = INF.
Вид ответа: d[E]. Сложность O(N2).

Так как определить таблицу для всех i нельзя, нужно использовать map: m[i] — минимальная стоимость стабильного интернета на интервале B..i. Сложность O(NlogN).