selfcompiler's blog

DP optimization Problem
By selfcompiler, 10 years ago, In English

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.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it +2 Vote: I do not like it

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.

→ Reply