[数据结构与算法]AtCoder Regular Contest 126 B-Cross-free Matching(最长上升子序列变形)

传送门

题意：

给出 $2\times n$ 个点，分别位于 $(1,0),(2,0),...,(n,0),(1,1),(2,1),,,,(n,1)$

有$m$条线段，连接上下两点 $(a_i,0),(b_i,1)$ ,要求选出最多的线段，使得两两不相交。

题解：

线段不相交要满足 $a_i<a_j$ 并且$b_i<b_j$

那么可以先把这些线段按照 $a_i$ 排序，然后就是选出最长的上升子序列$b_i$。

但是有一个要求，选出的线段中不能有重复的 $a_i$ ,即按照$a_i$分组，每组只能选一条。

为了防止出现同组内形成上升子序列而使得答案错误，可以将同组内的$b_i$ 按降序排序，这么同组内就不会形成上升子序列。

代码：

#pragma GCC diagnostic error "-std=c++11"
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<stack>
#include<set>
#include<ctime>
#define iss ios::sync_with_stdio(false)
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef pair<int,int> pii;
const int mod=1e9+7;
const int MAXN=2e5+5;
const int inf=0x3f3f3f3f;
struct node
{
    int a, b;
    /* data */
}f[MAXN];
int dp[MAXN];
bool cmp(node x,node y)
{
    if(x.a==y.a)
        return x.b > y.b;
    else
        return x.a < y.a;
}
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m;i++){
        scanf("%d%d", &f[i].a, &f[i].b);
    }
    sort(f + 1, f + 1 + m, cmp);
    memset(dp, inf, sizeof dp);
    int len = 0;
    for (int i = 1; i <= m;i++){
        *lower_bound(dp, dp + n, f[i].b) = f[i].b;
    }
    len = lower_bound(dp, dp + n, inf)-dp;
    printf("%d\n", len);
}