题解 | #信封嵌套#

补一个python3答案：

方法：

1. 按宽递增排序后，求长的最长严格上升子序列，同时要求宽不相等

注意：为保证宽不相等，可以使等宽区域内按长逆序排列，这样严格上升子序列在每组宽中只能取一个长，例：

输入排序前：
[[3, 4], [2, 3], [4, 5], [1, 3], [2, 2], [3, 6], [1, 2], [3, 2], [2, 4]]
排序后：
[[1, 3], [1, 2],
 [2, 4], [2, 3], [2, 2], 
 [3, 6], [3, 4], [3, 2], 
 [4, 5]
 ]

python3代码：

# 按宽递增排序后，求长的最长严格上升子序列，同时宽不相等(等宽区域内按长逆序排列即可)

def maxIncSub(arr,col=1):
    # @arr 传入数组
    # @col 按第col列求
    # @return 返回最长严格上升子序列的长度
    n=len(arr)
    dp=[1]*n
    for i in range(1,n):
        for j in range(i):
            if arr[j][col]<arr[i][col]:
                dp[i]=max(dp[i],dp[j]+1)
    return max(dp)


n=eval(input())
letters=[]
for _ in range(n):
    letters.append(list(map(int,input().split())))

# 先按长逆序，后按宽正序，即可使等宽区域内按长逆序排列
letters.sort(key=lambda x:x[1],reverse=True) # O(nlogn)
letters.sort(key=lambda x:x[0]) # 按宽排序 O(nlogn)

print(maxIncSub(letters,1))