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

最长公共子序列

Link

题目描述

给出 (1,2,ldots,n) 的两个排列 (P_1) 和 (P_2) ，求它们的最长公共子序列。

输入格式

第一行是一个数 (n)。

接下来两行，每行为 (n) 个数，为自然数 (1,2,ldots,n) 的一个排列。

输出格式

一个数，即最长公共子序列的长度。

输入输出样例

输入 #1

5 
3 2 1 4 5
1 2 3 4 5

输出 #1

说明/提示

对于 50% 的数据， (n le 10^3)；
对于 100% 的数据， (n le 10^5)。

我做这道题的时候心路历程是这样的：

这不是个模板题吗，水过去了 ---> wdnmd 这怎么 (TLE) 了------>看了一眼数据范围，我透，这题好狗啊。

先给出O（(n^2)）的转移方程吧：

设 (f[i][j]) 表示第一个串的前 (i) 位，第二个串的前 (j) 位的最长公共子序列的长度。

那么就有转移：

(a_i eq b_j) (f[i][j] = max(f[i-1][j],f[i][j-1],f[i][j]))
(a_i == b_j) (f[i][j] = max(f[i-1][j],f[i][j-1],f[i-1][j-1]+1,f[i][j]))

Code

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n;
int a[100010],b[100010];
int f[1010][1010];
int main(){
	scanf("%d",&n);
	for(int i = 1; i <= n; i++) scanf("%d",&a[i]);
	for(int j = 1; j <= n; j++) scanf("%d",&b[j]);
	f[0][1] = f[1][0] = 0;
	for(int i = 1; i <= n; i++)
        {
		for(int  j = 1; j <= n; j++)
               {
				f[i][j] = max(f[i][j],max(f[i-1][j],f[i][j-1]));
				if(a[i] == b[j])
                               {
					f[i][j] =max(f[i][j], f[i-1][j-1] + 1);
				}
		}
	}
	printf("%d",f[n][n]);
	return 0;
}

可这道题 (O(n^2)) 的数据显然过不去。

我们这就需要仔细观察一下这道题，然后你就会发现他有一个性质就是给出的两个序列都是排列。

这意味着什么？，也就是说 (p_1) 中的数一定·会在 (p_2) 中出现过。

所以，我们在 (p_1) 中排名靠前的数在 (p_2) 中排名也要靠前。

我们对 (p_1) 中得数求一下他在 (p_2) 出现的位置，然后求一个最长上升子序列就完事了。

Code：

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 1e5+10;
int n,ans,a[N],b[N],pos[N],tr[N];
int lowbit(int x){return x & -x;}
inline int read()
{
	int s = 0,w = 1; char ch = getchar();
	while(ch < '0' || ch > '9'){if(ch == '-') w = -1; ch = getchar();}
	while(ch >= '0' && ch <= '9'){s =s * 10+ch - '0'; ch = getchar();}
	return s * w;
}
void chenge(int x,int val)//树状数组查询前缀最大值
{
	for(; x <= N-5; x += lowbit(x)) tr[x] = max(tr[x],val);
}
int ask(int x)
{
	int res = 0;
	for(; x; x -= lowbit(x)) res = max(res,tr[x]);
	return res;
}
int main()
{
	n = read();
	for(int i = 1; i <= n; i++) a[i] = read();
	for(int i = 1; i <= n; i++)
	{
		b[i] = read();
		pos[b[i]] = i;
	}
	for(int i = 1; i <= n; i++) a[i] = pos[a[i]];//记录一下每个数在b中出现的位置
	for(int i = 1; i <= n; i++)
	{
		int tmp = ask(a[i]-1) + 1;
		chenge(a[i],tmp);
		ans = max(ans,tmp);
	}
	printf("%d
",ans);
	return 0;
}