匹配

匹配

描述

给定两个长度为 5n5n 的序列，其中 [1,n][1,n] 之间的所有数都出现了恰好 5 次。求它们的最长公共子序列长度。

输入

第一行一个整数 nn ，意义如题目描述。第二行 5n5n 个整数，表示序列 A。

第三行 5n5n 个整数，表示序列 B。

输

一行一个整数，表示序列 A 与序列 B 的最长公共子序列的长度。

输入样例 1

输样例 1

样例 1 解释

一种最长的公共子序列为 22112221 。

样例 2

点此下载。

限制

对于 50%的数据，1≤n≤10001≤n≤1000；

对于 100%的数据，1≤n≤200001≤n≤20000。

提示

[由于每种数都只出现了 5 次，我们考虑把每种数在A 中出现的位置作为第一维，在 B 中出现的位置作为第二维，就可以得到一个散点图。]

[那么我们现在就可以将问题转化为求平面上满足两维坐标都单调上升的最长点列的长度， 然后我们就可以 DP 辣。]

代码

#include <bits/stdc++.h> using namespace std; const int MAXN = 2e4 + 5;

int n, pos[MAXN][10], cnt[MAXN], a[MAXN * 5], dp[MAXN * 5]; int lowbit(int x) {

return x & -x;

}

int query(int p) {

int ret = 0;

while (p) {

ret = max(ret, dp[p]);

p -= lowbit(p);

}

return ret;

}

void update(int p, int x) {

while (p <= n * 5) {

dp[p] = max(dp[p], x);

p += lowbit(p);

}

}

int main() {

int x;

scanf("%d", &n);

for (int i = 1; i <= n * 5; ++i)

scanf("%d", &a[i]);

for (int i = 1; i <= n * 5; ++i) {

scanf("%d", &x);

pos[x][++cnt[x]] = i;

}

for (int i = 1; i <= n * 5; ++i)

for (int j = 5; j; --j) // 倒序更新，如果正序的话，会导致前面更新的答案被用来更新后面的 dp 值。

update(pos[a[i]][j], query(pos[a[i]][j] - 1) + 1); // 用树状数组维护区间最大值，dp[i]表示以i结尾的A数组和B数组的LCS

printf("%d\n", query(n * 5));

}