题解 | #信封嵌套#

1. 按照长度从小到大排序，当长度相同时，按照宽度从大到小排序。
2. 在宽度的维度上，动态规划求最长上升子序列的长度

为什么能这么做呢？

首先，宽度的维度上，动态规划求最长上升子序列 在长度方向上肯定也是 从小到大的。

这里面不存在相等的长度，因为本身上升子序列是一种递增的顺序，而如果长度相同了，它的对应的宽度是第减的（当长度相同时，按照宽度从大到小排序）。

这样就严格保证了 两边都是严格小于的

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int,int> ii ;
const int N = 2010;
vector<ii> scales;
int dp[N];
bool compare(const ii&a, const ii&b){
    if(a.first == b.first)
        return a.second>b.second;
    return a.first<b.first;
}
int main() {
    int n;
    cin >> n;
    for(int i=0;i<n;i++){
        int l,w;
        cin >> l >> w;
        scales.push_back({l,w});
        dp[i] = 1;
    }
    //先按 长度(pair_first)从 小到大排，当长度一样时，按宽度(pair_second)从大到小排
    sort(scales.begin(), scales.end(), compare);
    int res=0;
    //求 宽度上(pair_second)的最长递增子序列
    for(int i = 0;i<n;i++){
        for(int j=0;j<i;j++){
            if(scales[j].second < scales[i].second){
                dp[i] = max(dp[j]+1, dp[i]);
            }
        }
        if(dp[i]>res){
            res = dp[i];
        }
    }
    cout << res;
    return 0;
}
// 64 位输出请用 printf("%lld")