题目大意：有n*n个方格，王子有一条走法，依次经过m个格子，公主有一种走法，依次经过n个格子（不会重复走），问他们删去一些步数后，重叠步数的最大值。
显然是一个LCS，我一看到就高高兴兴的打了个板子上去，结果TLE+RE。
仔细一看：n<=250,那么二维数组就得开250*250*250*250了，显然RE了。
所以我想着用滚动数组来存储，但是TLE又拦住了我的去路。
O（n^2）的效率就是62500*62500，大于10^8，所以1s之内完不成，所以要想别的办法。
偶然在网上找到了O（nlogn）的求LCS方法，发现正是这道题所需的：
这种方法的核心是把LCS转化成LIS求解，时间效率就可以下降到nlogn。
条件是一个数列中不能有重复项（正好与题目条件相符）。
不多说直接讲如何转化：
设两个数组是a[maxn]与b[maxn]。
在读入a的时候，将每一个a[ i ]映射到i。（map[ a [ i ] ] = i）
在读入b的时候，用b[ i ]去映射里面找有无对应的值，并新开一个数组来求LIS。(dp[ i ]=map[ b [ i ] ])
此时我们思考一下dp数组表示的含义：如果dp[ i ]==0——>b[ i ]在a[ i ]中无对应的值，当然不计算在最后结果里。
dp[ i ]!=0——>说明b[ i ]与a[ i ]中第i个数相等.
显然我们可以看出，这里a[ i ],b[ i ]都不需要，只需要用一个变量来代替就可以了，而且dp[ i ]==0的情况也不用考虑，算LIS的时候不可能带上它。
所以通过以上的步骤，我们就把LCS转化成了LIS，接下来用O(nlogn)的LIS二分优化写法求dp数组的最长上升子序列就可以了。
上代码：
#include <cstdio>
#include<algorithm>
#include <cstring>
const int maxn = 250*250+10;
int n,len1,len2,ans,aa,bb,map[maxn],dp[maxn],low[maxn];
//map数组用来建立关联（直接用map容器也ok）
//dp数组用来储存新数列，并以他为基础求LIS
int main() {
int t;
scanf("%d", &t);//多组数据
for (int kk=1;kk<=t;kk++) {
memset(low, 0, sizeof(low));
memset(map, 0, sizeof(map));
memset(dp, 0, sizeof(dp));//每次开始计算新的一组时候要初始化。
scanf("%d%d%d", &n, &len1, &len2);//题目的一个坑 ，len1，len2是走的步数，实际上走的格数是步数加1
len1 ++; len2 ++; int cnt = 1;
for (int i = 1; i <= len1; i ++) {
scanf("%d", &aa);
map[aa] = i;
}
for (int i = 1; i <= len2; i ++) {
scanf("%d", &bb);
if (map[bb]) {
dp[cnt ++] = map[bb];
}//bb如果与之前的所有aa不存在关联，不用管他，有关联再算他
}
low[1] = dp[1]; ans = 1;
for (int i = 2; i <cnt; i ++) {
if (dp[i] > low[ans]) {
low[++ ans] = dp[i];
}
else {
int yy=std::lower_bound(low+1,low+ans+1,dp[i])-low;
low[yy] = dp[i];
}
}//这是二分优化LIS
printf("Case %d: %d\n", kk, ans);//注意输出格式，\n与space
}
return 0;
}
本题的主要思路就是LCS(n^2)------->LIS(nlogn)
一种压时间复杂度的好方法。