题意简述:

n 条光线从矩形上边的 n 个洞射入矩形区域后从下边的 n 个洞射出。

已知从第 i 个洞射入的光线编号为 x_i,从第 i 个洞射出的光线编号为 y_i,要求从这 n 条光线中选出最多数量的光线,使得这些光线中任意两条都会在矩形区域内相交。

思路分析

根据题意,所选光线按照射入洞口编号经过sort排序后,其射出洞口编号必然是倒序的。因此对所有光线按射入洞口编号排序后对其射出洞口编号求最长上升(不下降)子序列(即为 LIS)即可。

细节处理及注意事项

  1. 最大值最好开到 0x3f3f3f3f,这是int类型最大值;
  2. 不要类型定义 typedef pair<int,int> pii;,这样编译器会报错,如果一定要定义建议用 define 而不是 typedef

代码:

#include<bits/stdc++.h>

using namespace std;

const int INF=0x3f3f3f3f,N=1e6+5;

pair<int,int> p[N];
int a[N],dp[N],n;

inline int read() { //快读,加快输入速度
    int res=0,fh=1;
    char ch=getchar();
    while((ch>'9'||ch<'0')&&ch!='-')
        ch=getchar();
    if(ch=='-')
        fh=-1,ch=getchar();
    while(ch>='0'&&ch<='9')
        res=res*10+ch-'0',ch=getchar();
    return fh*res;
}

int LIS() {
    for(int i=1;i<n;++i)
        dp[i]=INF;
    dp[0]=a[0];
    int len=1;
    for(int i=1;i<n;++i)
        if(a[i]>dp[len-1])
            dp[len++]=a[i];
        else
            dp[lower_bound(dp,dp+n,a[i])-dp]=a[i]; 
    return len;
}

int main()  {
    scanf("%d",&n);
    for(int i=0;i<n;++i)
        a[read()-1]=i;
    for(int i=0;i<n;++i)
        p[i].first=a[i];
    for(int i=0;i<n;++i)
        a[read()-1]=i;
    for(int i=0;i<n;++i)
        p[i].second=a[i];
    sort(p,p+n);
    for(int i=0;i<n;++i)
        a[i]=p[n-1-i].second;
    printf("%d\n",LIS());
    return 0;
}
Categories: OI

0 Comments

Leave a Reply

Your email address will not be published. Required fields are marked *