原题链接
最长公共子序列的nlogn实现 本来想的是n^2结果一看数据范围傻眼了 300000 那n^2肯定白瞎啊 现学现用吧
设两组数列分别是s1 , s2 把s1里的元素 在s2中出现的位置记录下来 重复出现的将位置倒序排列 然后求最长上升子序列
/以下为引用内容
假设有两个序列 s1[ 1~6 ] = { a, b, c , a, d, c }, s2[ 1~7 ] = { c, a, b, e, d, a, b } 记录s1中每个元素在s2中出现的位置, 再将位置按降序排列, 则上面的例子可表示为： loc( a）= { 6, 2 } , loc( b ) = { 7, 3 } , loc( c ) = { 1 } , loc( d ) = { 5 } 将s1中每个元素的位置按s1中元素的顺序排列成一个序列s3 = { 6, 2, 7, 3, 1, 6, 2, 5, 1 } 在对s3求LIS得到的值即为求LCS的答案
#include<iostream> #include<cstring> #include<algorithm> #include<cstdio> #include<cmath> #include<queue> #include<vector> #include<climits> #include<string> #include<cstdlib> #include<map> #include<ctime> #define MAX 1000000007 #define LL long long using namespace std; map<int,int>q; int m,n,i,a[300005],b[300005],d[300005],len,pos[300005],p; int main() { scanf("%d%d",&n,&m); for(i=1;i<=n;i++) scanf("%d",&a[i]); for(i=1;i<=m;i++) { scanf("%d",&b[i]); q[b[i]]=i; } for(i=1;i<=n;i++) pos[i]=q[a[i]]; i=1; while(pos[i]==0) i++; d[1]=pos[i]; len=1; for(i=2;i<=n;i++) { if(pos[i]>d[len]) { len++; d[len]=pos[i]; } else { p=lower_bound(d,d+len+1,pos[i])-d; d[p]=pos[i]; } } printf("%d",len); return 0; }