題意:
有n個人每人有一個力氣值Si,美麗值Bi,滿足Bi>Bj&&Si>Sj 或者 Bi<Bj&&Si<Sj 的人可以
一起參見晚會,問最多有多少人可以一起參見晚會。
思路: 我們根據S從小到大将所有人排序,然後看B最長的上升子序列的長度求出來即可!
在排序中優先對S排序,S相等的則對B進行由大到小的排序,why?
也就是對于S相同的,我們先選取B最大的值插入LIS中,因為比如 S1=1, B1 = 1
S1=1, B1 = 2, S1=1, B1 = 3, 如果不進行排序,直接按照求B中的lis,顯然長度
為3,顯然是不對的,因為相同的S中隻能選擇一個B出來!是以就要對S相同的B進行
降序排序! 這樣就變成了一個裸lis!

View Code