题解 | #信封嵌套# 运算符重定义

#include <iostream>
#include <sstream>
#include <vector>
#include <algorithm>
using namespace std;
struct envelope{
    int height;
    int width;
    envelope(int w,int h):width(w),height(h){}
    bool operator<(envelope& other){
        if(width==other.width)return height<other.height;
        return width<other.width;
    };
    bool canHold(envelope& other){
        //cout<<*this<<' '<<other<< ((width>other.width) && (height>other.height))<<endl;
         return (width>other.width) && (height>other.height);
    }
    friend std::ostream& operator<<(ostream& os,envelope& ev){
        cout<<'('<<ev.width<<' '<<ev.height<<')';
        return os;
    };

};

int main() {
    int n;
    int t1,t2,i,j,result=1;
    //坑，result初值为1，与dp元素初值相同而不是随手写int_min，为了异常输入（n=1）时输出仍然为1
   cin>>n;
   vector<envelope> envelopes;envelopes.reserve(n);
   while(n-- && cin>>t1>>t2)envelopes.push_back({t1,t2});
   sort(envelopes.begin(),envelopes.end());
   vector<int> dp(envelopes.size(),1);
   //printa(envelopes);
   for(i=1;i<envelopes.size();++i){
    for(j=0;j<i;++j){
        if(envelopes[i].canHold(envelopes[j]))dp[i]=max(dp[i],dp[j]+1);
    }
    result=max(result,dp[i]);
   }
   cout<<result<<endl;
}
// 64 位输出请用 printf("%lld")