ACMP 661

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

• ACMP #661 — «Стабильный» интернет

Комментарии

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

Вид подзадачи: d[i][j] — минимальная стоимость стабильного интернета на интервале B..i, если использованы карты 1..j (карты упорядочены по времени).

Рекуррентная формула: d[k][j] = min(d[k][j], d[B_j][j - 1] + S_j), где k ∈ B_j..E_j.

База рекурсии: Если i <= l, то d[i][0] = 0, иначе d[i][0] = INF.

Вид ответа: d[E]. Сложность O(N²).

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