题解 | #小美打怪#

经典题目：最长递增子序列的变种。

我们先将满足所有小于和的放到一个数组中，然后按照第一维度降序排序，如果相等，那么升序排序。然后找出第二维的最长递减子序列就是我们的答案。

为什么需要相等的时候升序排序呢？ 因为题目要求了相等的不能够杀死，那么我们给他升序，那么找最长递减的时候就不可能选到。

这道题题目范围数据给的很小，只有,可以暴力dp,定义代表了数组的的最长递增子序列长度，转移方程如下:

这样转移时间复杂度为,然后还有二分或者使用树状数组优化达到，这里给出二分写法。

import sys

sys.setrecursionlimit(100010)

read = sys.stdin.readline

if __name__ == "__main__":
    """
        最长递减子序列
    """
    n,h,a = map(int,read().split())
    H = list(map(int,read().split()))
    A = list(map(int,read().split()))
    arr = []
    for x,y in zip(H,A):
        if x < h and y < a:
            arr.append((x,y))
    arr.sort(key=lambda x:(-x[0],x[1]))
    g = []
    for x,y in arr:
        l = 0
        r = len(g)
        while l < r:
            m = (l + r) >> 1
            if g[m] >= y:
                l = m + 1
            else:
                r = m
        if l == len(g):
            g.append(y)
        else:
            g[l] = y
    print(len(g))