P1439 【模板】最长公共子序列

本题链接：P1439 【模板】最长公共子序列

本博客给出本题截图：

AC代码

代码解释：
本题其实是一个 LIS 问题
二维状态量的话显然会TLE，这个题和其他的最长公共子序列不同的一点就是它只会包涵并且肯定包涵1 ~ n这些数，相当于P1数组和P2数组中的元素都是唯一对应，这里我们这样去处理：

我们把数组P1中的元素看成是一种顺序，那么本题要求的其实就变成了数组P2在数组P1的这种顺序下的最长上升子序列的长度，因为我们把P1数组看成了顺序，那么P2数组肯定就是单调上升的，那么P2数组中按照P1数组的排列方式下的上升子序列就是公共子序列

拿样例去举例说明：
例子中 P1数组：3 2 1 4 5，P2数组：1 2 3 4 5，我们设定a数组中的元素对应关系：3对应a，2对应b，1对应c，4对应d，5对应e，那么我们的P1数组就会变成：a b c d e，这就是一种新的顺序，那么P2数组就变成了：c b a d e，这就是P2数组在P1数组的顺序中的排列，故P1数组肯定满足单调上升，所以我们只要把P2数组中的最长上升子序列找出来，这个子序列的长度就是我们要求的最长公共子序列。

如何把P1数组设成我们的顺序呢：离散化思维去处理即可

代码：

#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 100010;

int b[N];
int p[N];
int f[N];
int n;

bool cmp(int u, int k)
{
	if (p[u] < p[k]) return true;
	return false;
}

int main()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; i ++ )
	{
		int x;
		scanf("%d", &x);
		p[x] = i;
	}
	for (int i = 1; i <= n; i ++ ) scanf("%d", &b[i]);
	
	int len = 0;
	for (int i = 1; i <= n; i ++ )
	{
		if (p[f[len]] < p[b[i]]) 
			f[++ len] = b[i];
		else 
		{
			int k = upper_bound(f + 1, f + len + 1, b[i], cmp) - f;
			f[k] = b[i];
		}
	}
	
	printf("%d\n", len);
	
	return 0;
}

文章来源: chen-ac.blog.csdn.net，作者：辰chen，版权归原作者所有，如需转载，请联系作者。

原文链接：chen-ac.blog.csdn.net/article/details/119829604