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

题目描述

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

输入输出格式

输入格式：

第一行是一个数n，

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

输出格式：

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

输入输出样例

输入样例#1： 复制

输出样例#1： 复制

说明

【数据规模】

对于50%的数据，n≤1000

对于100%的数据，n≤100000

题解：

刚开始看题以为是一道简单的LCS，但是一看数据到达的十万就知道不能用常规的LCS，之后一直在想新的方法，结果就是没有结果<_>

参考博客：https://pks-loving.blog.luogu.org/junior-dynamic-programming-dong-tai-gui-hua-chu-bu-ge-zhong-zi-xu-lie（里面还讲了一些LIS的nlogn和路径记录）

主要是没有对题目给出的条件充分利用，题目上说给出的两个序列中的数的范围是【1---n】，不能重复，只是第一个序列中的那个数在第二个序列中的位置不一样罢了

所以我们只需要找出来第一个序列中的每个位置得数在第二个序列中的位置就可以了

为什么呢？

因为我们要求的是两个序列的LCS，所以我们要求出来第一个序列与第二个序列最长相似部分，我们把第一个序列的每个数转化成在第二个序列的位置，到时候只需要求出来最长上升序列就可以（转化成了LIS）

例如：

2 4 1 5 3

1 2 4 3 5

把第一个序列转化：

2 3 1 5 4

找出来递增序列（最长）

2 3 5

发现在原序列中也是一样的

上代码：

 1 #include<stdio.h>

 2 #include<string.h>

 3 #include<iostream>

 4 #include<algorithm>

 5 using namespace std;

 6 const int maxn=100005;

 7 int dp[maxn],v[maxn],w[maxn],mapping[maxn];

 8 int main()

 9 {

10     int n;

11     scanf("%d",&n);

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

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

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

15     {

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

17         mapping[w[i]]=i;

18     }

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

20     {

21         v[i]=mapping[v[i]];

22     }

23     int len=0,maxx=0;

24     dp[++len]=v[1];

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

26     {

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

28         else

29         {

30             int temp=upper_bound(dp+1,dp+1+len,v[i])-dp;

31             dp[temp]=v[i];

32         }

33     }

34     maxx=len;

35     printf("%d\n",maxx);

36 }

我原本还准备求一下最长上升序列，再求最长下降序列，再去他们中间的最大值，但是这是不对的，因为我们要找出来第一个序列尽可能多的相似第二个序列

所以如果转化为位置之后序列是1 2 3 4 ... 这样的才是最长的。（下降的根本不用考虑）

要注意适合这种方法的要满足一定的条件

1、每个数只能出现一次

2、在范围内每个数有且且只能出现一次

巴特西