天天看點

AC_Dream 1216 G - Beautiful People

題意:

有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!

繼續閱讀