SovietPower 的题解讲的很清楚。Map或Hash映射后用nlogn求出LIS。这里只给出代码。
#include<cstdio> #include<cctype> #include<map> #include<algorithm> using namespace std; map<int,int> vis; inline long long read(){ long long num=0,f=1; char ch=getchar(); while(!isdigit(ch)){ if(ch=='-') f=-1; ch=getchar(); } while(isdigit(ch)){ num=num*10+ch-'0'; ch=getchar(); } return num*f; } int a[1000010]; int b[1000010]; int sot[1000010]; int f[1000000]; int size; int cnt; int check(int s){ int l=1,r=cnt; while(l<=r){ int mid=(l+r)>>1; if(f[mid]==s) return mid; if(f[mid]<s) l=mid+1; if(f[mid]>s) r=mid-1; } return l; } int main(){ int n=read(),m=read(); for(int i=1;i<=n;++i) a[i]=read(); for(int i=1;i<=m;++i) b[i]=read(); for(int i=1;i<=n;++i) vis[a[i]]=i; for(int i=1;i<=m;++i){ int S=vis[b[i]]; if(S>0) b[i]=S; else b[i]=0x7fffffff; } for(int i=1;i<=m;++i){ if(b[i]==0x7fffffff) continue; int pos=check(b[i]); f[pos]=b[i]; cnt=cnt<pos?pos:cnt; } printf("%d",cnt); return 0; }