【模板】最长公共子序列

题目描述

给出

1

,

2

,

…

,

n

1,2,\ldots,n

1,2,…,n 的两个排列

P

1

P_1

P1​ 和

P

2

P_2

P2​ ，求它们的最长公共子序列。

输入格式

第一行是一个数

n

n

n。

接下来两行，每行为

n

n

n 个数，为自然数

1

,

2

,

…

,

n

1,2,\ldots,n

1,2,…,n 的一个排列。

输出格式

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

样例 #1

样例输入 #1

<code>5

3 2 1 4 5

1 2 3 4 5

样例输出 #1

3

提示

对于

50

%

50\%

50% 的数据，

n

≤

1

0

3

n \le 10^3

n≤103；对于

100

%

100\%

100% 的数据，

n

≤

1

0

5

n \le 10^5

n≤105。

一、DPDPDP的意义以及线性动规简介

动态规划自古以来是DALAODALAODALAO凌虐萌新的分水岭，但有些OIer认为并没有这么重要——会打暴力，大不了记忆化。但是其实，动态规划学得好不好，可以彰显出一个OIerOIerOIer的基本素养——能否富有逻辑地思考一些问题，以及更重要的——能否将数学、算筹学（决策学）、数据结构合并成一个整体并且将其合理运用qwqqwqqwq。

而我们首先要了解的，便是综合难度在所有动规题里最为简单的线性动规了。线性动规既是一切动规的基础，同时也可以广泛解决生活中的各项问题——比如在我们所在的三维世界里，四维的时间就是不可逆式线性，比如我们需要决策在相同的时间内做价值尽量大的事情，该如何决策，最优解是什么——这就引出了动态规划的真正含义：

在一个困难的嵌套决策链中，决策出最优解。

二、动态规划性质浅谈

首先，动态规划和递推有些相似（尤其是线性动规），但是不同于递推的是：

递推求出的是数据，所以只是针对数据进行操作；而动态规划求出的是最优状态，所以必然也是针对状态的操作，而状态自然可以出现在最优解中，也可以不出现——这便是决策的特性（布尔性）。

其次，由于每个状态均可以由之前的状态演变形成，所以动态规划有可推导性，但同时，动态规划也有无后效性，即每个当前状态会且仅会决策出下一状态，而不直接对未来的所有状态负责，可以浅显的理解为——

_ Future  never  has  to  do  with  past  time  ,but  present  does.\mathcal{Future \ \ never \ \ has \ \ to \ \ do \ \ with \ \ past \ \ time \ \ ,but \ \ present \ \ does}.Future  never  has  to  do  with  past  time  ,but  present  does._

现在决定未来，未来与过去无关。

三、扯正题——子序列问题

（一）一个序列中的最长上升子序列（LISLISLIS）

例：由6个数，分别是： 1 7 6 2 3 4，求最长上升子序列。

评析：首先，我们要理解什么叫做最长上升子序列：1、最长上升子序列的元素不一定相邻 2、最长上升子序列一定是原序列的子集。所以这个例子中的LISLISLIS就是：1 2 3 4，共4个

1、n2n^2n2做法

首先我们要知道，对于每一个元素来说，最长上升子序列就是其本身。那我们便可以维护一个dpdpdp数组，使得**dp[i]dp[i]dp[i]表示以第iii元素为结尾的最长上升子序列长度**，那么对于每一个dp[i]dp[i]dp[i]而言，初始值即为111；

那么dp数组怎么求呢？我们可以对于每一个iii，枚举在iii之前的每一个元素jjj，然后对于每一个dp[j]dp[j]dp[j],如果元素iii大于元素jjj，那么就可以考虑继承，而最优解的得出则是依靠对于每一个继承而来的dpdpdp值，取maxmaxmax.

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

{

dp[i]=1;//初始化

for(int j=1;j<i;j++)//枚举i之前的每一个j

if(data[j]<data[i] && dp[i]<dp[j]+1)

//用if判断是否可以拼凑成上升子序列，

//并且判断当前状态是否优于之前枚举

//过的所有状态,如果是，则↓

dp[i]=dp[j]+1;//更新最优状态

}

最后，因为我们对于dpdpdp数组的定义是到i为止的最长上升子序列长度，所以我们最后对于整个序列，只需要输出dp[n]dp[n]dp[n](nnn为元素个数)即可。

从这个题我们也不难看出，状态转移方程可以如此定义：

下一状态最优值=最优比较函数（已经记录的最优值，可以由先前状态得出的最优值）

——即动态规划具有 判断性继承思想

2、nlognnlognnlogn 做法

我们其实不难看出，对于n2n^2n2做法而言，其实就是暴力枚举：将每个状态都分别比较一遍。但其实有些没有必要的状态的枚举，导致浪费许多时间，当元素个数到了104−10510^4-10^5104−105以上时，就已经超时了。而此时，我们可以通过另一种动态规划的方式来降低时间复杂度：

将原来的dp数组的存储由数值换成该序列中，上升子序列长度为i的上升子序列，的最小末尾数值

这其实就是一种几近贪心的思想：我们当前的上升子序列长度如果已经确定，那么如果这种长度的子序列的结尾元素越小，后面的元素就可以更方便地加入到这条我们臆测的、可作为结果、的上升子序列中。

qwq一定要好好看注释啊！

int n;

cin>>n;

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

{

cin>>a[i];

f[i]=0x7fffffff;

//初始值要设为INF

/*原因很简单，每遇到一个新的元素时，就跟已经记录的f数组当前所记录的最长

上升子序列的末尾元素相比较：如果小于此元素，那么就不断向前找，直到找到

一个刚好比它大的元素，替换；反之如果大于，么填到末尾元素的下一个q，INF

就是为了方便向后替换啊！*/

}

f[1]=a[1];

int len=1;//通过记录f数组的有效位数，求得个数

/*因为上文中所提到我们有可能要不断向前寻找，

所以可以采用二分查找的策略，这便是将时间复杂

度降成nlogn级别的关键因素。*/

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

{

int l=0,r=len,mid;

if(a[i]>f[len])f[++len]=a[i];

//如果刚好大于末尾，暂时向后顺次填充

else

{

while(l<r)

{

mid=(l+r)/2;

if(f[mid]>a[i])r=mid;

//如果仍然小于之前所记录的最小末尾，那么不断

//向前寻找(因为是最长上升子序列，所以f数组必

//然满足单调)

else l=mid+1;

}

f[l]=min(a[i],f[l]);//更新最小末尾

}

}

cout<<len;

Another  SituationAnother \ \ SituationAnother  Situation

但是事实上，nlognnlognnlogn做法偷了个懒，没有记录以每一个元素结尾的最长上升子序列长度。那么我们对于n2n^2n2的统计方案数，有很好想的如下代码（再对第一次的dpdpdp数组dpdpdp一次）：

for(i = 1; i <= N; i ++){

if(dp[i] == 1) f[i] = 1 ;

for(j = 1; j <= N: j ++)

if(base[i] > base[j] && dp[j] == dp[i] - 1) f[i] += f[j] ;

else if(base[i] == base[j] && dp[j] == dp[i]) f[i] = 0 ;

if(f[i] == ans) res ++ ;

}

但是nlognnlognnlogn呢？虽然好像也可以做，但是想的话会比较麻烦，在这里就暂时不讨论了qwqqwqqwq，但笔者说这件事的目的是为了再次论证一个观点:时间复杂度越高的算法越全能

333、输出路径

只要记录前驱，然后递归输出即可（也可以用栈的）

下面贴出n2n ^ 2n2的完整代码qwq

#include <iostream>

using namespace std;

const int MAXN = 1000 + 10;

int n, data[MAXN];

int dp[MAXN];

int from[MAXN];

void output(int x)

{

if(!x)return;

output(from[x]);

cout<<data[x]<<" ";

//迭代输出

}

int main()

{

cin>>n;

for(int i=1;i<=n;i++)cin>>data[i];

// DP

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

{

dp[i]=1;

from[i]=0;

for(int j=1;j<i;j++)

if(data[j]<data[i] && dp[i]<dp[j]+1)

{

dp[i]=dp[j]+1;

from[i]=j;//逐个记录前驱

}

}

int ans=dp[1], pos=1;

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

if(ans<dp[i])

{

ans=dp[i];

pos=i;//由于需要递归输出

//所以要记录最长上升子序列的最后一

//个元素，来不断回溯出路径来

}

cout<<ans<<endl;

output(pos);

return 0;

}

（二）两个序列中的最长公共子序列（LCSLCSLCS）

1、譬如给定2个序列：

1 2 3 4 5

3 2 1 4 5

试求出最长的公共子序列。

qwqqwqqwq显然长度是333，包含3  4  53 \ \ 4 \ \ 53  4  5 三个元素（不唯一）

解析：我们可以用dp[i][j]dp[i][j]dp[i][j]来表示第一个串的前iii位，第二个串的前j位的LCSLCSLCS的长度，那么我们是很容易想到状态转移方程的：

如果当前的A1[i]A1[i]A1[i]和A2[j]A2[j]A2[j]相同（即是有新的公共元素） 那么

dp[i][j]=max(dp[i][j],dp[i−1][j−1]+1);dp[ i ] [ j ] = max(dp[ i ] [ j ], dp[ i-1 ] [ j-1 ] + 1);dp[i][j]=max(dp[i][j],dp[i−1][j−1]+1);

如果不相同，即无法更新公共元素，考虑继承：

dp[i][j]=max(dp[i−1][j],dp[i][j−1]dp[ i ] [ j ] = max(dp[ i-1 ][ j ] , dp[ i ][ j-1 ] dp[i][j]=max(dp[i−1][j],dp[i][j−1]

那么代码:

#include<iostream>

using namespace std;

int dp[1001][1001],a1[2001],a2[2001],n,m;

int main()

{

//dp[i][j]表示两个串从头开始，直到第一个串的第i位

//和第二个串的第j位最多有多少个公共子元素

cin>>n>>m;

for(int i=1;i<=n;i++)scanf("%d",&a1[i]);

for(int i=1;i<=m;i++)scanf("%d",&a2[i]);

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

for(int j=1;j<=m;j++)

{

dp[i][j]=max(dp[i-1][j],dp[i][j-1]);

if(a1[i]==a2[j])

dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1);

//因为更新，所以++；

}

cout<<dp[n][m];

}

222、而对于洛谷P1439P1439P1439而言，不仅是卡上面的朴素算法，也考察到了全排列的性质：

对于这个题而言，朴素算法是n2n^2n2的，会被10510^5105卡死，所以我们可以考虑nlognnlognnlogn的做法：

因为两个序列都是1 n1~n1 n的全排列，那么两个序列元素互异且相同，也就是说只是位置不同罢了，那么我们通过一个mapmapmap数组将AAA序列的数字在BBB序列中的位置表示出来——

因为最长公共子序列是按位向后比对的，所以a序列每个元素在b序列中的位置如果递增，就说明b中的这个数在a中的这个数整体位置偏后，可以考虑纳入LCSLCSLCS——那么就可以转变成nlognnlognnlogn求用来记录新的位置的map数组中的**LISLISLIS**。

最后贴ACACAC代码：

#include<iostream>

#include<cstdio>

using namespace std;

int a[100001],b[100001],map[100001],f[100001];

int main()

{

int n;

cin>>n;

for(int i=1;i<=n;i++){ scanf("%d",&a[i]);map[a[i]]=i;}

for(int i=1;i<=n;i++){ scanf("%d",&b[i]);f[i]=0x7fffffff;}

int len=0;

f[0]=0;

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

{

int l=0,r=len,mid;

if(map[b[i]]>f[len])f[++len]=map[b[i]];

else

{

while(l<r)

{

mid=(l+r)/2;

if(f[mid]>map[b[i]])r=mid;

else l=mid+1;

}

f[l]=min(map[b[i]],f[l]);

}

}

cout<<len;

return 0

}

_ Although  there′re  difficulties  ahead  of  us  ,  remember  :\mathcal{Although \ \ there're \ \ difficulties \ \ ahead \ \ of \ \ us \ \ , \ \ remember \ \ :}Although  there′re  difficulties  ahead  of  us  ,  remember  : _

就算出走半生，归来仍要是少年