模板_最长公共子序列

Problem’s Website

【模板】最长公共子序列
Solution
P.s. : LIS = Longest Increasing Subsequence，最长上升子序列 LCS = Longest Common Subsequence，最长公共子序列
这道题是LCS问题
首先我们来考虑朴素一点的dp，设f[i][j]为第一个序列到i，第二个序列到j的LCS，答案为f[n][n]，状态转移方程显然得
1
2
3
4
if(a[i - 1] == b[j - 1])
f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
else
f[i][j] = max(f[i][j], max(f[i - 1][j], f[i][j - 1]));
这种方法的时间复杂度为θ(n^2)，对这道题来说，肯定会超时，但可以水过这道题Openjudge_1808:公共子序列
我们再来考虑正解，我们可以用一个数组Map[i]来记录i这个数在a[]中出现的位置，也就是离散化，然后LCS的长度为Map[b[i]]的LIS长度，因为离散化后，a[]数组相当于进行了升序排序，Map[b[i]]即a[i]==b[j]时，a[i]在a[]中的位置，对位置求出LIS，就相当于求出了a[]与b[]的LIS，关于LIS的求法，不会的见下文，这种方法的时间复杂度为θ(nlogn)，可以A掉这道题。
LIS问题

θ(n^2)的求法为设f[i]为到第i为的LIS长度，则基本代码为

   dp[1] = 1;
for(int i = 2; i <= n; i++) {
	dp[i] = 1;
	for(int j = 1; j <= i; j++) {
		if(a[i] > a[j] && dp[j] + 1 > dp[i])
			dp[i] = dp[j] + 1;
	}
}

优化。假设我们已经枚举到了i，下一位为j，如果a[j]>a[i]，那么LIS长度可以+1，如果a[j]<a[i]，我们可以二分找到在a[i]之前且刚好比a[j]大的数，用a[j]替换掉，运用人类智慧，显然这样是正确的，代码为
1
2
3
4
5
6
7
8
9
10
for(int i = 1; i <= n; i++) {
int x;
scanf("%d", &x);
if(x > a[top]) a[++top] = x;
else {
int id = upper_bound(a + 1, a + top + 1, x) - a;
a[id] = x;
}
}
printf("%d\n", top);

以上两种求LIS的方法都可以把Openjudge_1759:最长上升子序列水掉

Code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define gc getchar()
using namespace std;
int sc() {
	int xx = 0, ff = 1; char cch = gc;
	while(cch < '0' || cch > '9') {
		if(cch == '-') ff = -1; cch = gc;
	}
	while(cch >= '0' && cch <= '9') {
		xx = (xx << 1) + (xx << 3) + (cch ^ '0'); cch = gc;
	}
	return xx * ff;
}
int n, top;
int a[100010], b[100010], Map[100010], f[100010];
int main() {
	n = sc();
	for(int i = 1; i <= n; i++)
		a[i] = sc(), Map[a[i]] = i;
	for(int i = 1; i <= n; i++)
		b[i] = sc();
	for(int i = 1; i <= n; i++) {
		if(f[top] < Map[b[i]])
			f[++top] = Map[b[i]];
		else {
			int id = upper_bound(f + 1, f + top + 1, Map[b[i]]) - f;
			f[id] = Map[b[i]];
		}
	}
	printf("%d\n", top);
	return 0;
}

rp++

Problem’s Website

Solution

Code