Изменения
Перейти к:
навигация
,
поиск
← Предыдущая правка
Следующая правка →
Convex hull trick
4 байта добавлено
,
21:22, 18 января 2017
→
Наивное решение
'''for''' j = 1..i-1
'''if''' (dp[j] + a[i] <tex>\cdot</tex> c[j] < dp[i])
dp[i] = dp[j] + a[i] <tex>\cdot</tex> c[j]
'''return''' dp[n]
Нетрудно видеть, что такая динамика работает за <tex>O(n^2)</tex>.
Ololoshechkin
186
правок
Навигация
Персональные инструменты
Создать учётную запись
Войти
Пространства имён
Статья
Обсуждение
Варианты
Просмотры
Читать
Просмотр вики-текста
История
Ещё
Поиск
Навигация
Заглавная страница
Свежие правки
Случайная статья
Справка
Инструменты
Спецстраницы
Версия для печати