题目大意:给2个序列,求最长公共子序列。
题目分析:传统做法O(p*q),但此题p和q会很大,所以不能那样做。这题需要稍微转化一下,比较2个序列,将一个序列中的元素在另一个序列中出现的位置依次记录下来。对这个序列求一次LIS就可以了。hdu1025跟这个题其实是一个题。
详情请见代码:
#include <iostream> #include<cstdio> #include<cstring> using namespace std; const int N = 100000; int id[N],dp[N],lcm[N]; int n,p,q,num; int bin(int x,int r) { int l,mid,ret; l = 1; while(l <= r) { mid = (l + r)>>1; if(dp[mid] > x) r = mid - 1; else l = mid + 1; } return l; } int main() { int i,j,t,x; int cas = 0; scanf("%d",&t); while(t --) { scanf("%d%d%d",&n,&p,&q); num = 0; memset(id,0,sizeof(id)); for(i = 1;i <= p + 1;i ++) scanf("%d",&x),id[x] = i; for(i = 1;i <= q + 1;i ++) { scanf("%d",&x); if(id[x]) lcm[num ++] = id[x]; } int ans = 0; for(i = 0;i < num;i ++) { int tmp = bin(lcm[i],ans); dp[tmp] = lcm[i]; if(tmp > ans) ans ++; } printf("Case %d: %d\n",++ cas,ans); } return 0; }