搭积木

题目难度：三星
考察点：排序、最长不下降子序列（O(nlogn)）

方法1：排序、动态规划

1. 分析：
   根据题意，我们可以首先按照长度（或者是宽度）其中之一进行排序，那么我们接下来就只需要想办法将宽度搭积木的层数变得最多就可以了，将其转化为了最长不下降子序列（因为序列中是可以有相等的情况）的问题，我们就可以运用动态规划的思想进行操作。
   令dp[i]表示以a[i]结尾的最长不下降子序列长度。那么对于第i个来说就有两种可能：
   (1). 如果存在a[i]之前的元素a[j]，使得a[i] >= a[j]，那么就把a[i]放在以a[j]结尾的序列后面，找到了一条更长的不下降子序列，此时dp[i] = max(dp[i], dp[j]+1);
   (2). 如果a[i]之前的元素都比a[i]大，那么以a[i]为结尾的最长不下降子序列的长度只能为1。

算法实现：
(1). 首先用一个结构体数组保留长度和宽度。
(2). 按照某一维度（长度或者是宽度，这里以宽度为例）进行排序。
(3). 排序之后按照上述动态规划的方法进行求最长不下降子序列。
(4). 输出结果。

2. 复杂度分析：
   时间复杂度：O(n^2)
   空间复杂度：O(n)

3. 代码：

   #include <bits/stdc++.h>
   using namespace std;
   typedef long long LL;
   const int MAXN = 2e5+5;
   struct Node {
    int x, y;
   }a[MAXN];
   bool cmp(Node A, Node B) {
    if(A.x == B.x) return A.y < B.y;
    return A.x < B.x;
   }
   int dp[MAXN];
   int main() {
    int n; cin>>n;
    for(int i=0; i<n; i++) {
        cin>>a[i].x>>a[i].y;
        dp[i] = 1;
    }
    sort(a, a+n, cmp);
    int ans = 1;
    for(int i=1; i<n; i++) {
        for(int j=0; j<i; j++) {
            if(a[i].y >= a[j].y) dp[i] = max(dp[i], dp[j]+1);
        }
        ans = max(ans, dp[i]);
    }
    cout<<ans<<endl;
    return 0;
   }

方法：排序、贪心

1. 分析：
   这道题主要是在求最长不下降子序列的时候浪费的时间，那么我们就不用动态规划的算法求最长不下降子序列，用贪心的算法求最长不下降子序列，具体如下：
   我们可以充分利用数组的单调性，对于任意一个单调序列，如 1 2 3 4 5，如果向序列的尾部添加一个数x，我们只会关心x与最后一个元素即5的大小关系，因为只有最后一个数是有用的，具体实现方法就是利用一个数组dp，来表示每个序列的末尾元素，dp[i]表示长度为i的不下降子序列的最小末尾元素。
   那么对于当前的a[i]来说，就有如下两种情况:
   (1) a[i]>=dp[ans-1]，即a[i]比当前长度为ans的序列的最大值还大，那么此时显然要更新长度和序列，即dp[ans++] = a[i]
   (2) a[i]<dp[ans-1]，即a[i]比当前长度为ans的序列的最大值小，那么我们此时就要在当前长度为ans的序列中找到第一个大于a[i]的下标id，此时将此下标id的值替换为更小的a[i]。而这个在单调区间中找第一个大于a[i]的下标，显然可以用二分来操作。
   所以此方法的时间复杂度为O(nlog(n))

2. 复杂度分析：
   时间复杂度：O(nlog(n))
   空间复杂度：O(n)

3. 代码：

   #include <bits/stdc++.h>
   using namespace std;
   typedef long long LL;
   const int MAXN = 1e6+5;
   struct Node {
    int x, y;
   }a[MAXN];
   bool cmp(Node A, Node B) {
    if(A.x == B.x) return A.y < B.y;
    return A.x < B.x;
   }
   int dp[MAXN];
   int main() {
    int n; cin>>n;
    for(int i=0; i<n; i++) cin>>a[i].x>>a[i].y;
    sort(a, a+n, cmp);
    int ans = 0;
    dp[ans++] = a[0].y;
    for(int i=1; i<n; i++) {
        if(a[i].y >= dp[ans-1]) dp[ans++] = a[i].y;
        else {
            int id = upper_bound(dp, dp+ans, a[i].y)-dp;
            dp[id] = a[i].y;
        }
    }
    cout<<ans<<endl;
    return 0;
   }