GDUT寒假训练场2-最长公共子序列_随笔

GDUT寒假训练场2-最长公共子序列

题目描述

给出 1∼n 的两个排列 P1 和 P2，求它们的最长公共子序列。
输入格式
第一行是一个数 n (1≤n≤10^5)。

接下来两行，每行为 n 个数，为自然数1∼n 的一个排列。
输出格式
一个数，即最长公共子序列的长度。

输入样例

5

3 2 1 4 5

1 2 3 4 5

输出样例

3

参考思路

第一眼会以为这道题是真的求最长公共子序列，但是当我们写出最长公共子序列代码的时候会发现数组不够用了，10^5不支持我们开这么大的二维数组来求公共子序列。

那么怎么办呢？

我们发现两个序列都是1~n的全排列，那么两个序列元素互异且相同，也就是说只是位置不同罢了，那么我们通过一个m数组将A序列的数字在B序列中的位置表示出来，那么问题最变成了求最长上升子序列。

一位大佬的解释

关于为什么可以转化成LIS问题，这里提供一个解释。

A:3 2 1 4 5

B:1 2 3 4 5

我们不妨给它们重新标个号：把3标成a,把2标成b，把1标成c……于是变成：

A: a b c d e
B: c b a d e

这样标号之后，LCS长度显然不会改变。但是出现了一个性质：

两个序列的子序列，一定是A的子序列。而A本身就是单调递增的。
因此这个子序列是单调递增的。

换句话说，只要这个子序列在B中单调递增，它就是A的子序列。

哪个最长呢？当然是B的LIS最长。

自此完成转化。

参考代码

#define _CRT_SECURE_NO_WARNINGS
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
#define F 100005
int b[F], c[F], m[F];//c数组用来存最长上升子序列 m数组为记录出现顺序数组 
int main()
{
	int n;
	cin >> n;
	int date;
	for (int i = 1; i <= n; ++i)
	{
		scanf("%d", &date); m[date] = i;
	}
	for (int i = 1; i <= n; ++i)
	{
		scanf("%d", &date); b[i] = m[date];
	}
	//b已经成功构建 求b的最长上升子序列 
	//我们采用二分法来求最长上升子序列 
	c[1] = b[1];
	int len = 1;
	int flag = 0;
	for (int i = 2; i <= n; ++i)
	{
		if (b[i] > c[len])
		{
			c[++len] = b[i];
		}
		else
		{
			flag = lower_bound(c + 1, c + len, b[i]) - c;//二分查找等于或大于的元素下标 
			c[flag] = b[i];
		}
	}
	cout << len << endl;
	return 0;
}

题外音

如果不了解二分求最长上升子序列可以先去学习一下

二分求最长上升序列数组里面存放的不一定是真正的最长上升子序列

如果有更好的方法或者有错误的地方，欢迎斧正。

感谢您的阅读！(*^▽^*)

欢迎分享，转载请注明来源：内存溢出

原文地址: https://outofmemory.cn/zaji/5714629.html

GDUT寒假训练场2-最长公共子序列

发表评论

评论列表（0条）