题解 | #信封嵌套#

#这道题需要同时判断信封的长和宽，显得有些麻烦，如果能只处理一个就好了

#有这个思路就可以使用咱们万能的排序，先按长排序

#之后再按照最长递增子序列的方法来解决即可，当然，要注意一下宽的判断

#动态规划五部曲：确定dp含义、写出递推公式、初始化、遍历计算、debug

#dp[i]表示以a[i][0]这个长度为结尾的最长递增子序列长度

#递推公式：

#dp[i]=dp[j]+1 if a[i][0]>a[j][0] and a[i][1]>a[j][1] and dp[j]+1>dp[i] for j in range(i)

#显然，dp应该初始化为全1

#编码
n=int(input())
a=[]
for i in range(n):
    a.append([int(i) for i in input().split()])
# print(a)
#初始化
dp=[1 for i in range(n)]

#先排序
a=sorted(a,key=lambda x:x[0],reverse=False)
# print(a)

#遍历计算
for i in range(n):
    for j in range(i):
        if a[i][0]>a[j][0] and a[i][1]>a[j][1] and dp[j]+1>dp[i]:
            dp[i]=dp[j]+1

#输出结果
print(max(dp))