求解最长公共子序列

前置芝士

最长公共子序列的定义：两个序列长度最长的相同子序列，子序列是按照在原序列中出现顺序排序取出元素形成的序列。
P1341 最长上升子序列。
AT_dp_f LCS 暴力版

声明

将最长公共子序列称为 LCS，最长上升子序列称为 LIS。

给定序列

\{x_n\}=\{x_1,x_2,x_3···x_{n-1},x_n\}

，

\{y_n\}=\{y_1,y_2,y_3···y_{n-1},y_n\}

，两序列的 LCS 为

\{z_n\} = \{z_1,z_2,z_3···z_{k-1},z_m\}

。

暴力

使用 DP 枚举。

以序列的长度为阶段，枚举两个序列，我们考虑设状态

dp_{i,j}

表示子序列

\{x_i\}

，

\{y_j\}

的 LCS 的长度，

\{z_k\}

表示此时的 LCS。我们需要注意

dp_{i,j}

与

dp_{i-1,j-1},dp_{i-1,j},dp_{i,j-1}

的转移关系，以及

x_i

与

x_j

对前面转移关系的约束，因为这两个量的等量或不等关系决定了这两个元素是否在当前的 LCS 中，也是影响

dp_{i,j}

取值的。那么我们进行分类讨论！

若 $x_{i}=y_{j}$ ，那么 $x_{i},y_{j}$ 在 $dp_{i,j}$ 中，即 $z_k=x_i=y_j$ ， $\{z_{k-1}\}$ 是 $\{x_{i-1}\},\{y_{j-1}\}$ 的一个 LCS。
若 $x_{i}\neq y_{j}$ ，那么 $z_{k} \neq x_{i}$ ， $\{z_k\}$ 是 $\{x_{i-1}\}$ 与 $\{y_{j}\}$ 的一个 LCS。
若 $x_{i}\neq y_{j}$ ，那么 $z_{k} \neq y_{j}$ ， $\{z_k\}$ 是 $\{x_{i}\}$ 与 $\{y_{j-1}\}$ 的一个 LCS。

上述结论可由反证法严格证明。

dp_{i,j}=\begin{cases} dp_{i-1,j-1}+1 &if &x_i=y_i\\dp_{i-1,j} &if &x_i\neq y_i &and &dp_{i-1,j-1}\geq dp_{i,j-1} \\ dp_{i,j-1} &if &x_i\neq y_j &and &dp_{i-1,j-1}<dp_{i,j-1} \\ \end{cases}

由于

2,3

行中的

x_i\ne y_j

是同时存在的,有

dp_{i,j}=\begin{cases} dp_{i-1,j-1}+1 &if &x_i=y_i\\ \max \{dp_{i-1,j},dp_{i,j-1}\} &if &x_i\neq y_i \end{cases}

此时算法时间复杂度是

O(n^2)

级别，对于

n\le 10^5

的数据无法全部通过。

转化

另辟蹊径。

注意条件是给定两个排列！由于

\forall a_i,\forall b_i\in[1,n]

且每个元素出现且仅出现一次。

所以我们可以构造序列

\{c_{n}\}

，

c_i

表示元素

b_i

在

\{a_n\}

中的出现位置

id

，用代码表示就是 c[b[i]] = c[a[id]] = id ，我们举个例子。

n=6

\{x\}=\{5,1,3,2,6,4\}

\{y\}=\{1,5,3,2,6,4\}

\{c\}=\{2,1,3,4,6,5\}

例如对于

y_1=1

，

1

在

\{x\}

中的第

2

位出现，

c_i=2

，此时

x_{c_i} =x_{2}=y_1=1

，

y_1,x_2,c_1

，也就是

y_i,x_{id=c_i},c_i

是一组对应，

注意

\{c\}

的元素组成的子序列

\{2,3,4,6\}

，这是一个上升子序列，观察其在

\{y\}

，

\{x\}

的对应序列，

\{y\} = \{\red{1}, 5, \red{3}, \red{2}, \red{4}, 6\}

，

\{x\} = \{5, \red{1}, \red{3}, \red{2}, 6, \red{4}\}

，完全一样！

这里提供一个不严谨证明即可。

判断公共序列与具体位置无关，只考虑对应元素相等，满足先后顺序。
考虑 $\{c\}$ 中一个上升子序列的两个元素，满足 $c_i<c_j,i<j$ ，此时 $i\to id_1,j\to id_2$ （这里表示映射关系），即存在 $x_{id_1}=y_i,x_{id_2}=y_j$ ，那么对应的元素 $y_i$ 出现在 $y_j$ 前，元素 $x_{id_1}$ 出现在 $x_{id_2}$ 前，满足 $1$ 中的条件。
推而广之，我们就将求公共序列转化为求上升序列，当然是求最长上升子序列（LIS）。

二分求 LIS

求

\{c_n\}

的 LIS，且

O(n^2)

及时间复杂度更高的方法是不合法的。

还是考虑 DP，因为 LIS 中后续的数必须大于前一个数(请读者使用反证法自行证明)，令序列

\{dp_n\}

中

dp_i

表示长度为

i

的上升子序列的最小末尾（最后一个数的最小值），序列的最后一个存在值的下标应当是 LIS 的长度（重点！）。

请先思考上升子序列需要满足哪些条件！对于

\forall c_i,\forall c_j,i<j,需要c_i<c_j

我们需要不断更新这个序列（数组），我们以

i

（

[1,n]

）为阶段枚举。

注意序列应当单调递增

(1)

，我们枚举的顺序是

1\to n

(2)

(以下简称性质

(1),(2)

)。

由于 LIS 的长度未知，所以我们只关心

dp_{i_{max}}

的存在性，说人话就是只需找到最后一个

dp_i

的位置。

首先将

\{dp_n\}

全部值初始化为正无穷（不严谨说法）。

我们每次只进行两个操作。

取出当前 $c_i$ ，找到 $\{dp_n\}$ 中第一个大于等于它的数（这里就是二分），设这个数位置为 $pos\in[1,n]$ ，令 $dp_{pos} = c_i$ 。
更新答案， $ans=\max\{ans,pos\}$ .

简要说明 ：对于操作

1

，我们取出

c_i

利用了二分算法，即利用了性质

(1)

，由于性质

(2)

，操作时天然满足当前元素

dp_{pos}

在

dp_{pos-1}

之前，由于

dp_{pos}

是第一个大于等于的数，所以

dp_{pos-1}<c_i

，我们可以将

c_i

接入

dp_{pos-1}

所代表的最长公共子序列，我们保证了

\{dp_{pos}\}

具有性质

(1)

，同时保证了 LIS 一定被更新，也就是说找出了答案。

那么我们便获取了

dp_{pos}

的一个新的不劣的值。当然这里可以分类讨论，即

dp_{pos}

有值与无值，但两种情况下只需同样的更新操作，所以该讨论是不必要的。

我们回顾一下，首先考虑我们利用了性质

(2)

，这个性质是我们构造的，不变的，合法;那么对于性质

(1)

呢？可以看出我们只需要当前

\{dp_k\}

保持性质

(1)

，那么

\{dp_{k+1}\}

同样保持性质

(1)

，

\{dp_{k+2}\},\{dp_{k+3}\}···

也同理满足，那么只需保证

\{dp_1\}

符合性质

(1)

即可。那么

$请循其本!（return$ $back!）-庄子$

显然只含一个元素的

\{dp_1\}

必然符合单调性，那么我们也就做完了！

总结

算法时间复杂度为

O(n\log{n})

，足够通过本题。我们回顾本题，实际上该解法有一个特点，就是所设状态不在答案中，但这不妨碍我们利用问题的最优子结构做 DP，所以我认为洛谷题解区的贪心说法并不严谨。本文倾注了作者超过

5

小时的时间，也是个人认为对于该问题的最好解释（目前）了，希望给大家带来一些启发。

AC Code

CPP

#include<bits/stdc++.h>
using namespace std;
#define int long long//保险栓
const int N = 1e5 + 5;

struct node{
	int val,id;
}x[N],y[N];

int c[N],dp[N],n,ans = 0,o;
inline int read();//快读快写不必在意
inline void write(int x,bool op);
signed main(){
	n = read();
	for (int i=1; i<=n; i++) x[i].val = read(),x[i].id = i,c[x[i].val] = i;//构造 c 序列
	for (int i=1; i<=n; i++) y[i].val = read();
	memset(dp,0x77,sizeof dp);//初始化为无穷大
	dp[1] = c[y[1].val];
	int x,pos;
	for (int i=1; i<=n; i++){
		o = c[y[i].val];//取出 ci
		pos = lower_bound(dp+1,dp+n+1,o) - dp;//二分找,操作 1
		ans = max(ans,pos);//更新答案，操作 2
		dp[pos] = o;
	}
	write(ans,0);
	return 0;
}

//快读快写不必在意
inline int read(){
	int x = 0,f = 1;
	char ch = getchar();
	while (ch < '0' || ch > '9'){
		if (ch == '-') f = -1;
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9'){
		x = (x << 1) + (x << 3) + ch - '0';
		ch = getchar();
	}
	return x * f;
}
char rec[21];
inline void write(int x,bool op){
	if (x == 0){
		putchar('0');
		return ;
	}
	if (x < 0){
		x = -x;
		putchar('-');
	}
	int p = 0;
	while(x){
		rec[p++] = x % 10 + '0';
		x /= 10;
	}
	while(p--){
		putchar(rec[p]);
	}
	if (op){
		putchar(' ');
	}
}

特别鸣谢

@2011hym(本站同名)，好同学。

@Miracle_ZX 大佬，本文受到某篇启发。

完结撒花，制作不易，管理大大给个精品吧。

求解最长公共子序列

文章操作

前置芝士

声明

暴力

转化

二分求 LIS

总结

AC Code

特别鸣谢

相关推荐

评论

求解最长公共子序列