poj1065 偏序+LIS

/*
Time:2019.11.3
Author: Goven
type：偏序问题+LIS（最长下降子序列） 
err:
ref:不会：https://blog.csdn.net/AC_hell/article/details/51416840 
知识点：偏序序列 + lower_bound（二分查找） 
*/ 
#include<iostream>
#include<algorithm>
#define MAXN 5005
using namespace std;
struct Node {
    int l, w;
};
Node a[MAXN];
int dp[MAXN]; // 表示栈 
int top;
bool cmp(const Node &x, const Node &y) {
    if (x.l != y.l) return x.l < y.l;
    return x.w < y.w; 
}
int find(int v) {
    int l = 0, h = top;
    int mid;
    while (l <= h) {
        mid = (l + h) / 2;
        if (dp[mid] == v) return mid;//err1：漏了这一句，所以二分中一定要分三种情况 
        else if (dp[mid] < v) h = mid - 1;
        else l = mid + 1; 
    }
    return l;
}
int main()
{
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        for (int i = 0; i < n; i++) {
            cin >> a[i].l >> a[i].w;
        }
        sort(a, a + n, cmp);
        top = 0;
        dp[top] = a[0].w;
        for (int i = 1; i < n; i++) {
            if (dp[top] > a[i].w) dp[++top] = a[i].w;
            else {
                int tp = find(a[i].w);
                dp[tp] = a[i].w;
            }
        }
        top++;
        cout << top << endl;
    } 
    return 0;
}

//lower_bound 
#include<iostream>
#include<algorithm>
#include<functional> //greater<type>() 
#include<cstring>
#define MAXN 5005
using namespace std;
struct Node {
    int l, w;
};
Node a[MAXN];
int dp[MAXN]; // 表示栈 
int top;
bool cmp(const Node &x, const Node &y) {
    if (x.l != y.l) return x.l < y.l;
    return x.w < y.w; 
}
int main()
{
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        for (int i = 0; i < n; i++) {
            cin >> a[i].l >> a[i].w;
        }
        sort(a, a + n, cmp);
        memset(dp, 0, sizeof(dp));
        for (int i = 0; i < n; i++) {
            *lower_bound(dp, dp + n, a[i].w, greater<int>()) = a[i].w;
        }
        cout << lower_bound(dp, dp + n, 0, greater<int>()) - dp << endl;//找到第一个小于等于0的位置——即栈的top 
    } 
    return 0;
}