洛谷 P1439 【模板】最长公共子序列 题解

时间：2023-03-09 05:11:43
洛谷 P1439 【模板】最长公共子序列 题解

每日一题 day40 打卡

Analysis

因为两个序列都是1~n 的全排列，那么两个序列元素互异且相同，也就是说只是位置不同罢了，那么我们通过一个book数组将A序列的数字在B序列中的位置表示出来

因为最长公共子序列是按位向后比对的，所以a序列每个元素在b序列中的位置如果递增，就说明b中的这个数在a中的这个数整体位置偏后，可以考虑纳入LCS——那么就可以转变成nlogn求用来记录新的位置的book数组中的LIS。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #define maxn 100000+10

 #define INF 9187201950435737471

 #define rep(i,s,e) for(register int i=s;i<=e;++i)

 #define dwn(i,s,e) for(register int i=s;i>=e;--i)

 using namespace std;

 inline int read()

 {

     int x=;

     bool f=;

     char c=getchar();

     for(; !isdigit(c); c=getchar()) if(c=='-') f=;

     for(; isdigit(c); c=getchar()) x=(x<<)+(x<<)+c-'';

     if(f) return x;

     return -x;

 }

 inline void write(int x)

 {

     if(x<){putchar('-');x=-x;}

     if(x>)write(x/);

     putchar(x%+'');

 }

 int n,ans=;

 int a[maxn],b[maxn],book[maxn],last[maxn];

 signed main()

 {

     n=read();

     rep(i,,n) a[i]=read(),book[a[i]]=i;

     rep(i,,n) b[i]=read();

     last[]=book[b[]];

     rep(i,,n)

     {

         if(book[b[i]]>=last[ans]) last[++ans]=book[b[i]];

         else

         {

             int num=upper_bound(last+,last+ans+,book[b[i]])-last;

             last[num]=book[b[i]];

         }

     }

     write(ans);

     return ;

 }

请各位大佬斧正（反正我不认识斧正是什么意思）

相关文章