P1439 最长公共子序列（O（nlgn））

题目描述

给出1-n的两个排列P1和P2，求它们的最长公共子序列。

输入输出格式

输入格式：

 

第一行是一个数n，

接下来两行，每行为n个数，为自然数1-n的一个排列。

 

输出格式：

 

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

 

输入输出样例

输入样例#1： 复制

5 3 2 1 4 5 1 2 3 4 5

输出样例#1： 复制

3

说明

【数据规模】

对于50%的数据，n≤1000

对于100%的数据，n≤100000

 

思路：

经典的dp方法肯定解决不了这问题，那么我们首先看样例3 2 1 4 5 我们把他变成 1 2 3 4 5 用一个belong数组记录一下每个数字变成了什么，相当于离散化了一下3-1；2-2；1-3；4-4；5-5；

现在我们的第二串1 2 3 4 5 按我们离散化的表示：3 2 1 4 5

可能有些人已经懂了，我们把第一个串离散化后的数组是满足上升，反过来，满足上升的也就是满足原串的排列顺序的，那么结果就变成了一个求最长不下降子序列，直接使用O（nlgn）做法

#include<iostream> #include<cstdio> #include<algorithm> using namespace std; const int inf = 1e9 + 7; int n, num; const int maxn = 100000; int belong[maxn], A[maxn], B[maxn], C[maxn], g[maxn]; int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d", &A[i]); belong[A[i]] = i; //离散化，例如3 - 1 } for (int i = 1; i <= n; i++) scanf("%d", &B[i]); for (int i = 1; i <= n; i++) C[i] = belong[B[i]];//用C记录离散化后的数 fill(g, g + maxn, inf);//求解最长不下降子序列 for (int i = 1; i <= n; i++) { int index = upper_bound(g + 1, g + n + 1, C[i]) - g; g[index] = C[i]; } for (int i = 1; i <= n; i++) { if (g[i] != inf) num++; } cout << num << endl;//结束 return 0; }