题解

最长非降子序列问题描述： 给若干个数，输出这些数能组成的最长非降子序列的长度。如2,4,6,3,4,5,6的最长非降子序列为2,3,4,5,6。所以最长非降子序列长度为5。
最长非降子序列问题经典解法--动态规划DP--时间复杂度O(nlogn)

可以看出，每个非降子序列只有最后一个数的大小和位置（代表了该非降子序列的长度）至关重要！而非降子序列的其他数不太重要。通过观察可以用一个辅助数组dp存非降子序列相关信息，在input一个数num时
1）如果num大于等于dp最后一个元素，为了得到更长的非降子序列，应该将num直接添加到dp的最后
2）如果num不大于dp的最后一个元素，说明这个数无法加入当前最长非降子序列，但是这个数作为其他子序列的最后一个数，应该存下来，所以将dp中第一个大于num的数替换为num（就算只是dp的最后一个元素大于num，这个时候意味着num作为最后一个数的序列和当前最长非降子序列一样长，这种情况也应该替换，因为num更小，组成的非降子序列更紧凑，在后面更有潜力找到更长的非降子序列）

这样dp的长度就是最长非降子序列的长度

本题中因为长方形有长和宽两个参数，则先对长方形的宽w进行由小到大排序，从而将本题简化为对长l求最长非降子序列。

【注】调用库函数：ForwardIter lower_bound(ForwardIter first, ForwardIter last,const _Tp& val)算法返回一个非递减序列[first, last)中的第一个大于等于值val的位置。

#include<bits/stdc++.h>
using namespace std;
#define N 1000000

//定义矩形数组  
struct rectangle {
    int w = 0, l = 0;
} a[N];
int dp[N];

//矩形数组排序方式：先根据矩形宽从小到大排序，宽相同时按长从小到大排序 
bool cmp(rectangle x, rectangle y){
    return x.w == y.w ? x.l < y.l : x.w < y.w;
}

int main()
{
//输入矩形数据到数组中 
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) {
        cin >> a[i].w >> a[i].l;
    }
//对矩形数组进行排序 
    sort(a, a + n, cmp);
//求最长上升子序列的长度
    dp[0] = a[0].l;
    int len = 1;
    for(int i = 1; i < n; i++) {
        if(a[i].l >= dp[len-1]) {
            dp[len++] = a[i].l;
        } else {
            *(upper_bound(dp, dp + len, a[i].l)) = a[i].l;
        }
    }
    cout << len << endl;
    return 0;
}