有两个长度为p+1和q+1的序列，每个序列中的各个元素互不相同，且都是1~n*n之间的整数，两个序列的第一个元素都是1，，求a和b的最长公共子序列的长度。
思路很容易想到lcs，但是由于O（pq）的算法肯定会超时，所以不能采用，注意到a和b中的元素互不相同，故可以预处理a中的元素，用trans数组记录a每个元素值对应的位置，然后处理b中的元素，把每个元素转化成该元素在a中的位置，如果没在a中出现那么为零，这样就把lcs问题转化成了lis
#include<cstdio> #include<cstring> #include<cmath> #include<cstdlib> #include<iostream> #include<algorithm> #include<vector> #include<map> #include<queue> #include<stack> #include<string>#include<map> #include<set>#define eps 1e-6 #define LL long long using namespace std; const int maxn = 250 * 250 + 50;const int INF = 0x3f3f3f3f;int n, p, q;int B[maxn], trans[maxn], g[maxn], d[maxn];int kase = 0;void init() {scanf("%d%d%d", &n, &p, &q);memset(trans, 0, sizeof(trans));for(int i = 1; i <= p+1; i++) {int tmp; scanf("%d", &tmp);trans[tmp] = i;}for(int i = 0; i <= q; i++) {int tmp; scanf("%d", &tmp);B[i] = trans[tmp];}}void solve() {int ans = -INF;for(int i = 1; i <= q+1; i++) g[i] = INF;for(int i = 0; i <= q; i++) {int k = lower_bound(g+1, g+q+2, B[i]) – g;d[i] = k;g[k] = B[i];} for(int i = 0; i <= q; i++) ans = max(ans, d[i]);printf("Case %d: %d\n", ++kase, ans);}int main() {freopen("input.txt", "r", stdin);int t; scanf("%d", &t);while(t–) {init();solve();}return 0;}
累死累活不说，走马观花反而少了真实体验，
