Блог пользователя selfcompiler

Автор selfcompiler, 10 лет назад, По-английски

Can anyone Guide me how to optimize this relation  where b[j]>=b[j+1] and a[i]<=a[i+1] .I know for optimization use convex hull trick and i read convex hull trick ,but i don't know how to use this trick to optimize this Dp relation.

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
10 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Well initially start with an empty set of lines, then after you calculate dp(i) add the line Ax+B witb A=b(i) and B=dp(i). Then if at some point you want to calculate dp(i) then you just run a query with x=a(i). The b(j)<=b(j+1) allows adding lines without using a dynamic set and a(i)<=a(i+1) allows solving the problem using pointer walk on the set of lines instead of doing binary each time, thus reducing the running time to amortized O(1) per query.

Sorry for using () instead of [] im writing from a phone.