ACMP 631

Материал из Олимпиадное программирование в УлГТУ
Версия от 12:48, 11 января 2015; Ctrlalt (обсуждение | вклад)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)
Перейти к навигации Перейти к поиску

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

Похожие задачи

Комментарии

Неоптимальное решение за O(N2):

Вид подзадачи: d[i] — минимальное количество конфет для отгадывания числа i.
Рекуррентная формула: d[i] = min(max(d[i - j] + 2, d[j] + 1)), где j ∈ 1..(i - 1).
База рекурсии: d[1] = 0.
Вид ответа: d[n]. Сложность O(N2).

Решение за O(N):

Вид подзадачи: d[i] — минимальное количество конфет для отгадывания числа i; m[j] — максимальное число, для отгадывания которого нужно j конфет.
Рекуррентная формула: d[i] = max(d[i - x] + 2, d[x] + 1), где x = m[d[i - 1] - 1]).
База рекурсии: d[] = {0, 0, 2, 3, ...}; m[] = {1, 0, 2, 3, ...}.
Вид ответа: d[n]. Сложность O(N).