解法:
1. 用a2i建立a[] -> idx的索引
2. 用c[i]记录b中值为i的元素在a中的下标
3. 上题转化为LIS问题
4. 用q[i]记录长度为i的递增序列的末尾元素最小值,故q[]为单增序列
#include <iostream>
using namespace std;
const int N = 4000010;
int c[N];
int a2i[N];
int q[N], tt=0; // q[i]表示长度为i的递增序列的末尾元素最小值,故q[]单调递增
// tt for q.end()
int main() {
int ans = 0;
// LCS 2 LIS
int n; cin >> n;
for (int i = 1; i <= n; i++) {
int x; scanf("%d", &x);
a2i[x] = i;
}
for (int i = 1; i <= n; i++) {
int x; scanf("%d", &x);
c[i] = a2i[x];
}
// better LIS (nlogn)
for (int i = 1; i <= n; i++) {
if (c[i] == 0) continue;
int t = lower_bound(q, q+tt, c[i]) - q;
if (t == tt) q[tt++] = c[i];
else q[t] = c[i];
}
cout << tt << endl;
return 0;
}
v2: 自己实现lower_bound
/**
* LCS优化题
*
* 先将LCS问题转化为LIS问题
*/
#include <iostream>
using namespace std;
const int N = 4000010;
int c[N];
int a2i[N];
int q[N], tt=0; // q[i]表示长度为i的递增序列的末尾元素最小值,故q[]单调递增
int main() {
int ans = 0;
// LCS 2 LIS
int n; cin >> n;
for (int i = 1; i <= n; i++) {
int x; scanf("%d", &x);
a2i[x] = i;
}
for (int i = 1; i <= n; i++) {
int x; scanf("%d", &x);
c[i] = a2i[x];
}
// better LIS
for (int i = 1; i <= n; i++) {
if (c[i] == 0) continue;
int l = 0, r = tt;
while (l < r) {
int mid = l + r >> 1;
if (c[i] <= q[mid]) r = mid;
else l = mid + 1;
}
if (r == tt) q[tt++] = c[i];
else q[r] = c[i];
}
cout << tt << endl;
return 0;
}