问题简述: 两行有顺序的数找最长的公共子部分...
问题抽象: 将第二行的数映射成其在第一行的位置...那么问题就转化为了LCS....
LCS的nlogn解法:
用dp[ x ] 表示长度为 x 的子序列末尾最小可为的值...初始值dp[ x ]是很大的数...更新顺序为数列的左到右...这里有个很值得注意的情况...dp [ x ] 是非递减的....所以对于当前数..可以用二分来确定他能放的最长位置....
Program:
#include<iostream> #include<stdio.h> #include<string.h> #include<cmath> #include<algorithm> #include<map> #include<set> #include<queue> #define ll long long #define oo 1000000000 #define MAXN 62600 using namespace std; int mark[MAXN],dp[MAXN]; int main() { int T,t,n,p,q,x,i,l,r,mid; scanf("%d",&T); for (t=1;t<=T;t++) { scanf("%d%d%d",&n,&p,&q); memset(mark,0,sizeof(mark)); for (i=1;i<=p+1;i++) { scanf("%d",&x); mark[x]=i; } memset(dp,0x7f,sizeof(dp)); for (i=1;i<=q+1;i++) { scanf("%d",&x); x=mark[x]; if (!x) continue; l=0; r=n*n+1; while (r-l>1) { mid=(r+l)/2; if (dp[mid]<x) l=mid; else r=mid; } dp[l+1]=x; } for (i=n*n;i>=1;i--) if (dp[i]<=n*n) break; printf("Case %d: %d\n",t,i); } return 0; }