最长公共子序列

最长公共子序列

时间限制：1 sec

空间限制：256 MB

问题描述

给定两个 1 到 n 的排列 A,B （即长度为 n 的序列，其中 [1,n] 之间的所有数都出现了恰好一次）。

求它们的最长公共子序列长度。

输入格式

第一行一个整数 n ，意义见题目描述。

第二行 n 个用空格隔开的正整数 A[1],…,A[n]，描述排列 A。第三行 n 个用空格隔开的正整数 B[1],…,B[n]，描述排列 B。

输格式

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

样例输入

样例输

样例解释

(2,3) 和 (2,4) 都可以是这两个序列的最长公共子序列。

数据范围

对于 80%   的数据，保证 n<=5,000。对于 100% 的数据，保证 n<=50,000。

提示

[把 A 中的所有数替换成其在 B 中出现的位置，想一想，新序列的最长上升子序列和所求的东西有什么关系呢？]

代码

#include <iostream> #include <vector> #include <algorithm>

#pragma warning(disable:4996) using namespace std;

// ================= 代码实现开始 =================

/* 请在这里定义你需要的全局变量 */

const int inf = 1e9;

//pos:b中各元素出现位置

//f:f[i]表示长度为i的最长公共子序列的末尾最小可能元素vector<int> pos, f;

// 计算最长公共子序列的长度

// n：表示两序列长度

// a：描述序列 a（这里需要注意的是，由于 a 的下标从 1 开始，因此 a[0] 的值为-1，你可以忽略它的值，只需知道我们从下标 1 开始存放有效信息即可）  

// b：描述序列b（同样地，b[0] 的值为 -1）

// 返回值：最长公共子序列的长度

int LCS(int n, vector<int> a, vector<int> b) {

/* 请在这里设计你的算法 */

//初始化，调整pos,f数组的长度，并将f数组置初值

pos.resize(n + 1);

f.resize(n + 2, inf);

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

pos[b[i]] = i;//记录b序列中各元素出现位置

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

a[i] = pos[a[i]];

f[0] = 0;//将f[0]置为0

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

*lower_bound(f.begin(), f.end(), a[i]) = a[i];

return int(lower_bound(f.begin(), f.end(), n + 1) - f.begin()) - 1;

}

// ================= 代码实现结束 =================

int main() {

int n, tmp;

vector<int> a, b;

scanf("%d", &n);

a.clear();

b.clear();

a.push_back(-1);

b.push_back(-1);

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

scanf("%d", &tmp);

a.push_back(tmp);

}

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

scanf("%d", &tmp);

b.push_back(tmp);

}

int ans = LCS(n, a, b);

printf("%d\n", ans);

return 0;

}