浅谈LIS和LCS

这是一篇由超级菜的OIer写的博客……

LIS就是最长上升子序列，通过DP求解。
普通的求法是\(O({n}^{2})\)的(相信大家都会写)：

解法1

#include <bits/stdc++.h>
using namespace std;
const int N = 105, inf = 1e9 + 10;
int a[N], f[N];
int n, ans = -inf;
int main() {
	cin >> n;
	for (int i = 1; i <= n; i ++) {cin >> a[i]; f[i] = 1;}
	for (int i = 1; i <= n; i ++)
		for (int j = 1; j < i; j ++)
			if (a[i] > a[j]) f[i] = max(f[i], f[j] + 1);
	for (int i = 1; i <= n; i ++)
		ans = max(ans, f[i]);
	cout << ans << '\n';
	return 0;
}

n如果比较大，这种做法当然就不行了。
有一种基于贪心的二分求解方法，我们维护一个最长上升序列，扫描a[i], a[i]>序列末尾的数，加进去，序列长度+1；如果a[i] <=序列末尾，我们可以通过二分找到序列中第一个大等于a[i]的数，用a[i]替换掉它（相当于在不改变序列单调性的前提下使某一个数减小），这就是基于贪心思想的求法，最后序列的长度也就是我们要找的LIS。

解法2

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, inf = 1e9 + 10;
int f[N], a[N];
int n, ans;
int main() {
	cin >> n;
	for (int i = 1; i <= n; i ++) cin >> a[i], f[i] = inf;
	f[1] = a[1];
	ans = 1;//初始答案
	for (int i = 2; i <= n; i ++) {
		if (a[i] > f[ans]) f[++ ans] = a[i];
		else f[lower_bound(f + 1, f + ans + 1, a[i]) - f] = a[i];
	}
	cout << ans << '\n'; 
}

这样复杂度就优化成\(O(nlogn)\)了。

还有没有其他做法呢？众所周知，算法的魅力有很大一部分在于寻找不断优化的过程，我们进一步分析DP过程，f[i] = max(f[j] + 1, f[i]) (a[j] < a[i], j < i),而我们每次更新f[i]时，都要枚举1~i-1的所有j,这是很大的浪费。我们可以用树状数组优化，
对于每个a[i]，查询它前面最大的f[j]，f[i] = f[j] + 1,再向树状数组a[i]位置中插入f[i]，该树状数组以值域为下标，维护的是最大的f[j]。复杂度同样是\(O(nlogn)\), 如果数值较大，记得离散化。

解法3

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, c[N], f[N], a[N];
void add(int x, int y) {
	while (x < N) {
		c[x] = max(c[x], y);
		x += x & (-x);
	}
}
int query(int x) {
	int res = 0;
	while(x) {
		res = max(res, c[x]);
		x -= x & (-x);
	}
	return res;
}
signed main() {
	cin >> n;
	for (int i = 1; i <= n; i ++) cin >> a[i];
	for (int i = 1; i <= n; i ++) {
		f[i] = query(a[i]) + 1;
		add(a[i], f[i]);
	}
	int ans = 0;
	for (int i = 1; i <= n; i ++) ans = max(ans, f[i]);
	cout << ans << '\n';
}

LCS最长公共子序列。给你两个序列，求他们的最长公共部分。

常规解法：

#include <bits/stdc++.h>
using namespace std;
const int N = 5010;
int a[N], b[N], f[N][N], n, m;
int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i ++) cin >> a[i];
	for (int i = 1; i <= m; i ++) cin >> b[i];
	for (int i = 1; i <= n; i ++) {
		for (int j = 1; j <= m; j ++) {
			f[i][j] = max(f[i - 1][j], f[i][j - 1]);
			if (a[i] == b[j]) f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
		}
	}
	cout << f[n][m];
}

n较大时这种解法肯定不能用了，此时题目应该还会给其他条件。
看一道题：
P1439 【模板】最长公共子序列
两个序列是相同长度n，且其中的元素范围都是1~n，观察n可以取到\(10 ^ 5\),那么上面的方法肯定不能用，我们可以将a序列每个元素映射为编号，这样a序列就是1~n，对于b采用a的映射方式，问题就转化为了求b的最长上升子序列了，采用二分的方式。

代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, inf = 1e9 + 10;
int n, a[N], b[N], mp[N], f[N];
int main() {
	cin >> n;
	for (int i = 1; i <= n; i ++) {cin >> a[i]; mp[a[i]] = i;}
	for (int i = 1; i <= n; i ++) {cin >> b[i]; f[i] = inf;}
	int len = 0;
	for (int i = 1; i <= n; i ++) {
		if (mp[b[i]] > f[len]) f[++ len] = mp[b[i]];
		else f[lower_bound(f + 1, f + len + 1, mp[b[i]]) - f] = mp[b[i]];
		//找f数组中第一个>=mp[b[i]]的位置。 
	}
	cout << len << '\n';
	return 0;
}