[UVa 10635]Prince and Princess
转载请注明出处：http://danihao123.is-programmer.com/
这个名字真有童话风味哎……
直接LCS肯定会TLE。注意每个序列都是不重复序列，所以可以将A映射到[tex][1,p+1][/tex]，然后再把B映射一下（有的可能A里面没有？反正既然A里没有就和LCS没关系了），就相当于求B的LIS。LIS可以在[tex]O(nlogn)[/tex]时间内完成。
代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=62510;
#define CL_ARR(x,v) memset(x,v,sizeof(x))
int B[maxn];
int Hash[maxn];
int d[maxn],g[maxn];
int main(){
int T,n,p,q,x;
register int i,ans,k,Case=0;
scanf("%d",&T);
while(T--){
Case++;
scanf("%d%d%d",&n,&p,&q);
CL_ARR(Hash,0);
for(i=1;i<=(p+1);i++){
scanf("%d",&x);
Hash[x]=i;
}
for(i=1;i<=(q+1);i++){
scanf("%d",&x);
B[i]=Hash[x];
}
CL_ARR(g,0x7f);
ans=0;
for(i=1;i<=(q+1);i++){
k=lower_bound(g+1,g+2+q,B[i])-g;
d[i]=k;
g[k]=B[i];
ans=max(ans,d[i]);
}
printf("Case %d: %d\n",Case,ans);
}
return 0;
}
评论 (0)
