Can't understand the convex hull trick/optimization

Правка en1, от pizza_hot, 2016-08-23 23:47:40

Hi Everyone !

I was studying convex hull trick from here

I understood the main idea but I didn't understand the solution for the problem ACQUIRE

My question is :

they sorted rectangles by height in ascending order (if they are equal put the rectangle with the largest weight first)

and this is their pseudo code:

input N
for i=1 to N
     input rect[i].h
     input rect[i].w
let cost[0] = 0
for i=1 to N
     let cost[i] = OO
     for j=0 to i-1
         cost[i] = min(cost[i],cost[j]+rect[i].h*rect[j+1].w)
print cost[N]

but it's not necessary for every j<i : rect[j].w >rect[i].w (because we are comparing by the height first)

can someone tell me why did they do this ? :/

or have you got a better explain for the solution ?

sorry for my bad english , thanks in advance

Теги convex hull optimization, dp, dynamic programming

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский pizza_hot 2016-08-23 23:47:40 972 Initial revision (published)