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