1.题目描述：点击打开链接
2.解题思路：本题是一道经典的题目，巧妙的将LCS问题转化为LIS问题。这种题目的一个特定就是其中一个序列的所有元素均不相同。首先，我们可以对A数组重新编号为{1,2,3,…n}，接下来对于B数组的每个元素，，替换为A中那个元素的编号，若没有在A中出现，那么直接置0，这样，B数组也变为一个由编号构成的数组，此时我们发现，A数组是一个自然序列，那么只要在B中找到最长上升的子序列，就是和A的最长公共子序列！这就是本题的巧妙之处！而LIS问题有O(N*logN)的解法，因此可以通过本题的数据规模。
3.代码：
#define _CRT_SECURE_NO_WARNINGS #include<iostream>#include<algorithm>#include<string>#include<sstream>#include<set>#include<vector>#include<stack>#include<map>#include<queue>#include<deque>#include<cstdlib>#include<cstdio>#include<cstring>#include<cmath>#include<ctime>#include<functional>using namespace std;typedef long long ll;typedef unsigned long long ull;typedef pair<int, int> P;typedef pair<long long, long long> PL;#define me(s) memset(s,0,sizeof(s))#define For(i,n) for(int i=0;i<(n);i++)const int N = 250 * 250;const int INF = 1000000000;int S[N], g[N], d[N];int num[N];int main(){//freopen("t.txt", "r", stdin);int T;scanf("%d", &T);for (int rnd = 1; rnd <= T; rnd++){int n, p, q, x;scanf("%d%d%d", &n, &p, &q);me(num);for (int i = 1; i <= p + 1; i++){scanf("%d", &x); num[x] = i;//重新编号为1,2,3,…n}int cnt = 0;for (int i = 0; i < q + 1; i++){scanf("%d", &x);if (num[x])S[cnt++] = num[x];//将B数组的元素也修改为编号}fill(g + 1, g + cnt + 1, INF);//以下部分即为求解LIS问题的算法int ans = 0;For(i, cnt){int k = lower_bound(g + 1, g + cnt + 1, S[i]) – g;d[i] = k;g[k] = S[i];ans = max(ans, d[i]);}printf("Case %d: %d\n", rnd, ans);}return 0;}
渐渐少了联络，友谊就变的淡了，所以，抽点时间，联络朋友一起聊聊天，
