荒芜知地

Knowhere

0%

LIS & LCS

发表于 分类于 Valine：

LIS & LCS

问题描述

有两个序列 A 和 B。
求序列 A 的 LIS(最长上升子序列) 和 序列 A、B 的 LCS(最长公共子序列) 的长度。
注意，LIS 为严格递增的，即 a1 < a2 < … < ak (ai ≤ 1,000,000,000)。

Input

第一行两个数 n, m（1 ≤ n ≤ 5000, 1 ≤ m ≤ 5000）
第二行n个数，表示序列A
第三行m个数，表示序列B

Output

输出一行数据 ans1 和 ans2，分别代表序列 A 的 LIS 和序列 A、B 的 LCS 的长度

Sample

Input: 

Output:

Limitation

Time limit      1000 ms
Memory limit    1048576 kb

解题思路

LIS

(以下算法参考了 geeksforgeeks)

举个例子，数组 {3, 5, 4}，明显 LIS 是 {3, 5} 或 {3, 4}。

此时若加入元素 {7, 9}，即 {3, 5, 4, 7, 9}，LIS 为 {3, 5, 7, 9} 或 {3, 4, 7, 9}。

此时加入元素 {8}，即 {3, 5, 4, 7, 9, 8}，8 比原来的任何一个 LIS 的最小元素都大，但比原来的 LIS 的最大元素小，因此，8具有替代原来 LIS 的潜在可能。如果加入的是 1，明显 1 无法加入原来的 LIS，但它却具有构成新的 LIS 的可能，比如加入 {1, 2, 3, 4, 5, 6}，即 {3, 5, 4, 7, 9, 1, 2, 3, 4, 5, 6}，LIS 是 {1, 2, 3, 4, 5, 6}。

由此可得，长 LIS 可以看成一个短 LIS 与另一个符合的短 LIS 的组合，随着数组的遍历，合成了一个更加符合的长 LIS。

拿 {3, 7, 5} 来说，{3, 5} 比 {3, 7} 更有可能成为下一个加入元素的 LIS 的开端，因为 5 < 7，比如此时加入 6，即 {3, 7, 5, 6}，明显 LIS 是 {3, 5, 6}，而 {3, 7} 与 {6} 无法合并。

因此得出以下算法：

  1. 若 A[i] 比原来存的潜在 LIS 的最小元素都小，则将其成为新的潜在 LIS 的开端。
  2. 若 A[i] 比原来存的某个/某些潜在 LIS 的最大元素大，则将对应的潜在 LIS 序列复制，并加入 A[i]。
  3. 若 A[i] 不大不小，则将原来那些潜在 LIS 中可让 A[i] 加入的序列复制，并加入 A[i]。同时只保留与此新序列等长的且潜在 LIS 尾端元素最小的序列。

Wiki 上的例子 {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15} ：

A[0] = 0. Case 1. 无潜在 LIS，创建之。
0.
----------------------------------------
A[1] = 8. Case 2. 复制并加入。
0.
0, 8.
----------------------------------------
A[2] = 4. Case 3. 复制，加入，并舍弃。
0.
0, 4.
舍弃<0, 8>.
----------------------------------------
A[3] = 12. Case 2.
0.
0, 4.
0, 4, 12.
----------------------------------------
A[4] = 2. Case 3.
0.
0, 2.
舍弃<0, 4>.
0, 4, 12.
----------------------------------------
A[5] = 10. Case 3.
0.
0, 2.
0, 2, 10.
舍弃<0, 4, 12>.
----------------------------------------
A[6] = 6. Case 3.
0.
0, 2.
0, 2, 6.
舍弃<0, 2, 10>.
----------------------------------------
A[7] = 14. Case 2.
0.
0, 2.
0, 2, 6.
0, 2, 6, 14.
----------------------------------------
A[8] = 1. Case 3.
0.
0, 1.
舍弃<0, 2>.
0, 2, 6.
0, 2, 6, 14.
----------------------------------------
A[9] = 9. Case 3.
0.
0, 1.
0, 2, 6.
0, 2, 6, 9.
舍弃<0, 2, 6, 14>.
----------------------------------------
A[10] = 5. Case 3.
0.
0, 1.
0, 1, 5.
舍弃<0, 2, 6>.
0, 2, 6, 9.
----------------------------------------
A[11] = 13. Case 2.
0.
0, 1.
0, 1, 5.
0, 2, 6, 9.
0, 2, 6, 9, 13.
----------------------------------------
A[12] = 3. Case 3.
0.
0, 1.
0, 1, 3.
舍弃<0, 1, 5>.
0, 2, 6, 9.
0, 2, 6, 9, 13.
----------------------------------------
A[13] = 11. Case 3.
0.
0, 1.
0, 1, 3.
0, 2, 6, 9.
0, 2, 6, 9, 11.
舍弃<0, 2, 6, 9, 13>.
----------------------------------------
A[14] = 7. Case 3.
0.
0, 1.
0, 1, 3.
0, 1, 3, 7.
舍弃<0, 2, 6, 9>.
0, 2, 6, 9, 11.
----------------------------------------
A[15] = 15. Case 2.
0.
0, 1.
0, 1, 3.
0, 1, 3, 7.
0, 2, 6, 9, 11.
0, 2, 6, 9, 11, 15.
----------------------------------------
LIS 为 0, 2, 6, 9, 11, 15.

LISDemo.gif

(图片来源 Wikipedia)

LCS

用一个二维数组 f[m][n] 表示 A1..m, B1..n 的 LCS 长度。

初始时 f[1][0] = f[0][1] = f[0][0] = 0。若 Ai = Bj，f[i][j] = f[i-1][j-1] + 1，否则 f[i][j] = max(f[i-1][j], f[i][j-1])

比如说， “agree” 和 “aggregate”，最后一个字母相同，则 f["agree"]["aggregate"] = f["agre"]["aggregat"] + 1。
“cardiac” 和 “ordinal”，最后一个字母不同，则 f["cardiac"]["ordinal"] = max(f["cardia"]["ordinal"], f["cardiac"]["ordina"])。

源代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int ceilIndex(vector<int>& v, int l, int r, int key) {
	while (r - l > 1) {
		int m = l + (r - l) / 2;
		if (v[m] >= key)
			r = m;
		else
			l = m;
	}
	return r;
}

int lis(vector<int>& v) {
	if (v.size() == 0)
		return 0;

	vector<int> tail(v.size(), 0);
	int length = 1;
	tail[0] = v[0];
	for (int i = 1; i != v.size(); i++) {
		if (v[i] < tail[0])
			tail[0] = v[i];

		else if (v[i] > tail[length - 1])
			tail[length++] = v[i];

		else
			tail[ceilIndex(tail, -1, length - 1, v[i])] = v[i];
	}

	return length;
}

int lcs(vector<int>& v1, vector<int>& v2) {
	int m = v1.size();
	int n = v2.size();
	int** L = new int* [m + 10];
	for (int i = 0; i < m + 10; i++)
		L[i] = new int[n + 10];

	for (int i = 0; i <= m; i++) {
		for (int j = 0; j <= n; j++) {
			if (i == 0 || j == 0)
				L[i][j] = 0;
			else if (v1[i - 1] == v2[j - 1])
				L[i][j] = L[i - 1][j - 1] + 1;
			else
				L[i][j] = max(L[i - 1][j], L[i][j - 1]);
		}
	}

	return L[m][n];
}

int main() {
	int m, n;
	cin >> m >> n;
	vector<int> v1;
	vector<int> v2;
	for (int i = 0; i < m; i++) {
		int a;
		cin >> a;
		v1.push_back(a);
	}
	for (int i = 0; i < n; i++) {
		int a;
		cin >> a;
		v2.push_back(a);
	}
	int ans1 = lis(v1);
	int ans2 = lcs(v1, v2);
	cout << ans1 << " " << ans2 << endl;

	return 0;
}