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
Read observation 1 about irrelevant rectangles.
Suppose that both of rectangle A's dimensions equal or exceed the corresponding dimensions of rectangle B. Then, we may remove rectangle B from the input because its presence cannot affect the answer, because we can merely compute an optimal solution without it and then insert it into whichever subset contains rectangle A without changing the cost.Since the rectangles are then sorted by height, the width of the rectangles must be strictly decreasing. Otherwise, there exists two adjacent rectangles in the sorted list where the rectangle on the right has both a larger height and a larger width, which is impossible because the rectangle on the left is irrelevant and should have been removed.