Description
俄罗斯套信封问题，给定\(n\)封信，每一封信\(i\)有长宽\(h_i, w_i\)，每一封信嵌套要求长宽均满足严格递增关系，问最多能嵌套多少封信
Constraints
时间复杂度不超过\(O(nlogn)\)
Solution
二维LIS，使用排序降低维度，后面就是LIS模板
\(O(nlogn)\)的LIS忘记怎么写了，翻了下书
它的定义是比较特殊的：设\(dp[i]\)为长度为\(i+1\)的上升子序列中末尾元素的最小值
Code
class Solution {
public:
int maxEnvelopes(vector<vector<int>>& envelopes) {
auto &es = envelopes;
// Note: b[1] < a[1]，这样避免第一维相同时选了递增的二维
sort(es.begin(), es.end(), [](auto &a, auto &b) {
return tie(a[0], b[1]) < tie(b[0], a[1]);
});
constexpr int INF = 1<<30;
vector<int> dp(es.size(), INF);
for(auto &e : es) {
*lower_bound(dp.begin(), dp.end(), e[1]) = e[1];
}
return lower_bound(dp.begin(), dp.end(), INF) - dp.begin();
}
};