Изменения

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

186

правок