题解 | #信封嵌套# 动态规划前先排序

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 2010;
int n, dp[N];

struct letter {
    int a;
    int b;
};

letter let[N];

bool cmp(letter x, letter y) {
    return x.a > y.a;
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> let[i].a >> let[i].b;
        dp[i] = 1;
    }

    sort(let, let + n, cmp);
//  cout << endl;
//  for(int i=0; i<n; i++)
//      cout << let[i].a << " " << let[i].b << endl;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if ( let[i].a < let[j].a && let[i].b < let[j].b )
                dp[i] = max(dp[i], dp[j] + 1);
        }
    }

    int res = 0;
    for (int i = 0; i < n; i++)
        res = max( res, dp[i] );
    cout << res << endl;

    return 0;
}