给你两条路径，对于每条路径上的点各不相同，请你求出两条路径最长公共部分的长度。
Input
第一行是数据组数t 每组数据的第一行包含三个数，n,p,q。其中路径上的点的大小不会超过n^2. 第二行包含p+1个数，表示第一条路径 第三行包含q+1个数，表示第二条路径。
Output
输出最长路径长度。
冲上去写了个LCS，死在250^2的数据范围之下
正解是LIS
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 using namespace std; 5 const int maxn=250*250+2; 6 const int INF=1e9+5; 7 int t,n,q,p,x,tot,cas,a[maxn],b[maxn],c[maxn],d[maxn]; 8 template <class t>void red(t &x) 9 { 10 x=0; 11 int w=1; 12 char ch=getchar(); 13 while(ch<'0'||ch>'9') 14 { 15 if(ch=='-') 16 w=-1; 17 ch=getchar(); 18 } 19 while(ch>='0'&&ch<='9') 20 { 21 x=(x<<3)+(x<<1)+ch-'0'; 22 ch=getchar(); 23 } 24 x*=w; 25 } 26 void input() 27 { 28 freopen("input.txt","r",stdin); 29 //freopen("output.txt","w",stdout); 30 } 31 int main() 32 { 33 //input(); 34 red(t); 35 while(t--) 36 { 37 ++cas; 38 printf("Case %d: ",cas); 39 red(n); 40 red(p); 41 red(q); 42 memset(c,0,sizeof(c)); 43 memset(d,0x3f,sizeof(d)); 44 for(int i=1;i<=p+1;++i) 45 { 46 red(a[i]); 47 c[a[i]]=i; 48 } 49 for(int i=1;i<=q+1;++i) 50 { 51 red(x); 52 b[i]=c[x]; 53 } 54 tot=0; 55 d[++tot]=b[1]; 56 for(int i=2;i<=q+1;++i) 57 { 58 if(!b[i]) 59 continue; 60 if(b[i]>d[tot]) 61 d[++tot]=b[i]; 62 else 63 { 64 int j=lower_bound(d+1,d+tot+1,b[i])-d; 65 d[j]=b[i]; 66 } 67 } 68 printf("%d ",tot); 69 } 70 return 0; 71 }