本文共 1660 字，大约阅读时间需要 5 分钟。
题意：求最长公共子序列
正常的算法O(n^2)不够快，但因为这题数据特殊，数组中的数各不相同，可以转化成求最大上升子序列
比如样例中A{1 7 5 4 8 3 9}， B{1 4 3 5 6 2 8 9}，将数字重新映射编号map[ai]=i;
ai=map[ai];bi=map[bi];
变成A{1,2,3,4,5,6,7} B{1,4,6,3,0,0,5,7} 问题便变成了求B的LIS可以在0（nlogn）求出
// #pragma comment(linker, "/STACK:1024000000,1024000000")#include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;typedef long long ll;typedef pair pii;#define pb(a) push_back(a)#define INF 0x1f1f1f1f#define lson idx<<1,l,mid#define rson idx<<1|1,mid+1,rvoid debug(){#ifdef ONLINE_JUDGE#else freopen("d:\\in.txt","r",stdin); freopen("d:\\out1.txt","w",stdout);#endif}char getch(){ char ch; while((ch=getchar())!=EOF) { if(ch!=' '&&ch!='\n')return ch; } return EOF;}struct point{ int x,y,t; point() {} point (int a,int b,int e) { x=a; y=b; t=e; } bool operator < (point a) const { return t>a.t; }};int da[70000];int dp[70000];int lis(int n) //LIS的O(nlogn)算法{ int maxx=1; dp[1]=da[1]; for(int i=2;i<=n;i++) { if(da[i]>=dp[maxx]) { dp[++maxx]=da[i]; } else { int v=upper_bound(dp+1,dp+1+maxx,da[i])-dp; dp[v]=da[i]; } } return maxx;}int main(){ int t; scanf("%d",&t); for(int ca=1;ca<=t;ca++) { map ma; int n,a,b; scanf("%d%d%d",&n,&a,&b); for(int i=1;i<=a+1;i++) { int x; scanf("%d",&x); ma[x]=i; } int k=0; for(int i=1;i<=b+1;i++) { int x; scanf("%d",&x); int v=ma[x]; if(v!=0)//0表示没出现，没必要加进去了 da[++k]=v; } int num=lis(k); printf("Case %d: %d\n",ca,num); } return 0;}
转载于:https://www.cnblogs.com/BMan/p/3249120.html
