HDU 1069 - Monkey and Banana
Problem : Given n rectangles with three edge a[i], b[i] and c[i]. Find the highest heap, such that the below rectange has strictly smaller height and width than the higher rectangle.
Solution :
1. The best solution can be arranged by this format: { w[0], h[0], t[0] }, { w[1], h[1], t[1] }, ..., { w[k], h[k], t[k] } s.t. w[0]<=h[0]&&w[1]<=h[1]&&...&&w[k]<=h[k] and sum(t[i]) is maximum. Since if there exist a solution that one of the rectangle has w[i]>h[i], exchange them makes the solution still valid.
With the optimization 1, there are only 3n rectangles with { w[i], h[i], t[i] } should be considered.

2. Sort the rectangle in following way: The smaller w rectangle goes first, if w is the same, the larger h rectangle goes first. After sorting, the problem becomes the maximum valued sum increasing subsequence. The base sequence is h, the valued sequence is t.
proof of #2:
property 1: after sorting, h[i]>h[j] && w[i]>w[j] then i>j.
property 2: after sorting, h[i]>h[j] && i>j then w[i]>w[j].
-> : Each valid heap order in original problem is also in h increasing order in the sorted rectangle. According to property 1.
<- : Each h increasing subsequence is also a valid heap order in original problem. According to property 2.
[]
Merge branch 'master' of git@github.com:MissAmour/KrwlngsACMFile