天天看點

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!

AC_Dream 1216 G - Beautiful People
AC_Dream 1216 G - Beautiful People

View Code

繼續閱讀