[UVa 10635]Prince and Princess
转载请注明出处:http://danihao123.is-programmer.com/
这个名字真有童话风味哎……
直接LCS肯定会TLE。注意每个序列都是不重复序列,所以可以将A映射到,然后再把B映射一下(有的可能A里面没有?反正既然A里没有就和LCS没关系了),就相当于求B的LIS。LIS可以在
时间内完成。
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 | #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; } |