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.