【Luogu P1439】最长公共子序列（LCS）

Luogu P1439

令f[i][j]表示a的前i个元素与b的前j个元素的最长公共子序列

可以得到状态转移方程:

if (a[i]==b[j]) dp[i][j]=dp[i-1][j-1]+1;

dp[i][j]=max(dp[i][j],dp[i-1][j],dp[i][j-1]);

时空复杂度都为O(n²)

对于本题这种做法显然是无法接受的。

我们可以对这个题目进行转化。仔细看题，可以发现a,b两个序列都是1-n的排列。

那么，我们可以利用映射，将a中的数一一映射成为1,2,3,4,5……,n

再把b中的数一一对应更改。由于a中的数是升序的，所以b中的最长上升子序列的长度就是a与b的最长公共子序列。LCS问题就转化成了LIS问题。

例如样例

a的 3 2 1 4 5映射为1 2 3 4 5

则b从1 2 3 4 5变为3 2 1 4 5

结合上面的分析就会变得很容易理解了。

#include<algorithm>

#include<cstdio>

using namespace std;

int n,a[100005],b[100005],k[100005],dp[100005],ans;

int main()

{

	scanf("%d",&n);

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

	{

		scanf("%d",&a[i]);

		k[a[i]]=i;

	}

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

	{

		scanf("%d",&b[i]);

		b[i]=k[b[i]];

	}

	dp[1]=1;

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

	{

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

		{

			if (b[i]>b[j]) dp[i]=max(dp[i],dp[j]+1);

			else dp[i]=max(1,dp[i]);

		}

	}

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

		ans=max(ans,dp[i]);

	printf("%d",ans);

	return 0;

}

这个动态规划可以很轻松地写出来，但是我们发现时间还是不够优秀。

那么我们就要对这个算法进行优化。对于LIS问题，有一种广为人知的O(nlogn)的解法。

dp[i]中存储长度为i的LIS的最后一个数。

如果符合单调上升就直接增长长度并记录，否则就利用STL二分查找出dp数组中第一个大于b[i]的位置，替换它。

举个例子，例如 3 6 2 4 7 8

一开始的序列{3}，接着变成{3,6}

遇到2之后我们将3替换{2,6}，为什么可以进行替换呢？

因为后面还有一个4可以替换掉6，构成一条更优的序列。（保证结尾尽可能小，就能保证序列尽可能优）

如果后面没有4呢？那么也没有关系，因为这个2即使修改了也对答案没有任何影响。

（想一想为什么）

dp[1]=b[1];

len=1;

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

{

	if (b[i]>dp[len]) dp[++len]=b[i];//记录并增长长度。

	else

	{

		int x=upper_bound(dp+1,dp+1+len,b[i])-dp;

		dp[x]=b[i];

		//利用STL二分查找出dp数组中第一个大于b[i]的位置，替换它。

	}

}

完整代码如下：

#include<algorithm>

#include<cstdio>

using namespace std;

int n,a[100005],b[100005],k[100005],dp[100005],ans,len;

int main()

{

	scanf("%d",&n);

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

	{

		scanf("%d",&a[i]);

		k[a[i]]=i;//映射

	}

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

	{

		scanf("%d",&b[i]);

		b[i]=k[b[i]];//对应修改

	}

	dp[1]=b[1];

	len=1;

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

	{

		if (b[i]>dp[len]) dp[++len]=b[i];

		else

		{

			int x=upper_bound(dp+1,dp+1+len,b[i])-dp;

			dp[x]=b[i];

		}

	}

	printf("%d",len);

	return 0;

}

巴特西

【Luogu P1439】最长公共子序列（LCS）

最新文章

热门文章