题解 | #信封嵌套#

解题思路：

对等于求解最长上升子序列，先将输入按照升序排列。然后求解。 对于当前信封i有：

• 在此之前多所有嵌套只要满足v[i].first > v[j].first && v[i].second > v[j].second记录下最大的嵌套数，然后把i信封套入，dp[i]+1.
• 读了一次假题，多此一举地讲信封的长宽做了调整，保证first>second然后就错了，其实题目可以考虑这一层。

#include<bits/stdc++.h>
using namespace std;
int solve(vector<pair<int,int>> &v, vector<int> &dp, int n){//递归写法
    if(dp[n] != 0) return dp[n];
    if(n == 0) dp[n] = 1;
    else{
        int mx = 0;
        for(int i = 0; i < n; ++i){
            int tmp = solve(v, dp, i);
            if(v[n].first > v[i].first && v[n].second > v[i].second)
                mx = max(tmp,mx);
        }
        dp[n] = mx + 1;
        
    }
    return dp[n];
}
void solve2(vector<pair<int, int>> &v, vector<int> &dp){//递推写法
    dp[0] = 1;
    int i, j;
    for(i = 1; i < v.size(); ++i){
        int mx = 0;
        for(j = 0; j < i; ++j){
            if(v[i].first > v[j].first && v[i].second > v[j].second)
                mx = max(dp[j], mx);
        }
        dp[i] = mx + 1;
    }
}
int main(){
    int n;
    cin >>n;
    vector<pair<int, int>> v(n);
    for(int i = 0; i < n; ++i){
        // int a, b; //对应的假题操作
        // cin>>a;
        // cin>>b;
        // v[i].first = max(a,b);
        // v[i].second = min(a,b);
        cin>>v[i].first;
        cin>>v[i].second;
    }
    vector<int> dp(n);
    sort(v.begin(), v.end());
    solve(v, dp, n-1);
    // solve2(v, dp);
    int max_cnt = 0;
    for(int i = 0; i < n; ++i){
        max_cnt = max(max_cnt, dp[i]);
    }
    cout<<max_cnt<<endl;
    return 0;
}