题目大意:求序列a与序列b的最大连续公共子序列。
解题思路:动态规划,a[temp]表示序列a以temp为末端的最长连续增大序列的长度。a[temp] = a[temp-1] + 1,这是由于输入序列a第一个数时,以这个数为末端的最长连续增大序列的长度肯定为1,之后序列a中的数,根据记录过temp-1的长度基础+1,如果没有记录过自然也是1,否则则是记录时的长度加1。这就是基于连续的规律。结果就根据序列b记录时每次判断,对应序列a中,以temp为末端的最长连续增大序列。
ac代码:
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int t, a[1000005], b[1000005], n, m, ans, temp;
int main()
{scanf("%d", &t);while (t--){scanf("%d%d", &n, &m);ans = 0;memset(a, 0, sizeof(a)); memset(b, 0, sizeof(b));for (int i = 1; i <= n; i++){scanf("%d", &temp);a[temp] = a[temp - 1] + 1;}for (int i = 1; i <= m; i++){scanf("%d", &temp);b[temp] = b[temp - 1] + 1;ans = max(ans, min(a[temp], b[temp]));}printf("%d\n", ans);}return 0;
}