题目链接
题目大意
给定两个序列 a, b，求它们的最长公共子序列，这个子序列必须是值连续递增的，如 3, 4, 5, 6 。
解题思路
本题给出了一个限制条件，即子序列是值连续递增的序列，无形之中降低了难度。我们可以用数组 c 来表示以 1, 2, …, i, … 结尾的最长值连续递增子序列的长度，不难看出 c[i] = c[i-1]+1 。于是，我们只需要把原序列从头到尾扫一遍即可得到 c 数组。
栗如，a 序列为：1, 3, 2, 3, 5 ，扫一遍原序列即可得到以 i 结尾的最长值连续递增子序列的长度 ca[i]：
ca[1] = 1;
ca[3] = ca[2] + 1 = 1;
ca[2] = ca[1] + 1 = 2;
ca[3] = ca[2] + 1 = 3;
ca[5] = ca[4] + 1 = 1;
求出序列 a, b 对应的 ca, cb 数组之后，它们以 i 结尾的公共最长值连续递增子序列长度为 ca[i], cb[i] 中值较小的一个，即 min(ca[i], cb[i]) 。我们只需要遍历从 1 遍历到 10^5（题目中 a[i], b[i] 的最大值是 10^6，实际测试数据中不超过 10^5，如果真的按它的 10^6 做很容易被卡超时，也是醉了，厉害了我的出题哥），找寻最大值即可。
参考代码
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 100000;
int a[MAXN+1], b[MAXN+1];
int ca[MAXN+1], cb[MAXN+1];
int main(int argc, char const *argv[]) {
int t, n, m;
scanf("%d", &t);
while(t--) {
scanf("%d %d", &n, &m);
memset(ca, 0, sizeof ca);
memset(cb, 0, sizeof cb);
for(int i=0; i<n; ++i) {
scanf("%d", &a[i]);
ca[a[i]] = ca[a[i]-1] + 1;
}
for(int i=0; i<m; ++i) {
scanf("%d", &b[i]);
cb[b[i]] = cb[b[i]-1] + 1;
}
int ans = 0;
for(int i=1; i<=MAXN; ++i) {
ans = max(ans, min(ca[i], cb[i]));
}
printf("%d\n", ans);
}
return 0;
}