洛谷 P1439 【模板】最长公共子序列 【一题掌握和分清LCS和LIS】

前言

想做一题轻松的，于是就选了这个叫做最长公共子序列的模板题，但是它不讲武德，公共子序列只是幌子，最长上升子序列才是本题的关键。

题目

题目描述

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

输入格式

第一行是一个数 $n$。

接下来两行，每行为 $n$ 个数，为自然数 $1,2,\dots ,n$ 的一个排列。

输出格式

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

样例 #1

样例输入 #1

5 
3 2 1 4 5
1 2 3 4 5
1
2
3

样例输出 #1

3
1

提示

• 对于 $50\%$ 的数据， $n\le 10^3$；
• 对于 $100\%$ 的数据， $n\le 10^5$。

题目分析

  题目名字太坏了，当我老实地写了最长公共子序列试图通过时却不行。所以我直接傻了。于是就去看了一下大佬的解析才发现了隐藏在LCS中的LIS。
  首先明白一个概念，最长公共子序列的长度与符号无关，比如我举一个例子，求下列的最长公共子序列，很明显，它的最长公共子序列是{2、1、4}或{2、1、5}，长度为3

5 
3 2 1 4 5
2 1 3 5 4
1
2
3

其实我们可以看成是字母：1-A,2-B,3-C,4-D,5-E，于是就变成了下面的两个字符串

C B A D E
B A C E D
1
2

明显地，它的的最长公共子序列是{B、A、E}或{B、A、D},，长度也为3，甚至连映射关系都是一样的，所以我们得出结论，两个字符串的公共子序列长度与字符的表达无关，或者说映射关系同样成立，同样长度。可以于是我们假设一组映射关系使得3 2 1 4 5对应 1 2 3 4 5这个递增序列。比如3-1，2-2，3-1，4-4，5-5，于是乎第二个序列就为2 3 1 5 4，想要求{3 2 1 4 5}和{2 1 3 5 4}的最长公共子序列就等价于求{1 2 3 4 5}和{2 3 1 5 4}的最长公共子序列。于是就相当于求{2 3 1 5 4}的最长上升子序列。于是所有序列都可以做如上转换，将第一个序列转化为从1到n的递增序列，将第二个序列转化为想同映射后的序列，并求第二个序列转化后的序列的最长上升子序列。酷!

最长上升子序列的求法

注意事项

1.映射关系需要在输入的时候进行处理
2.数组要开大点不然RE和WA都是有可能的

代码

LCS最长公共子序列模板（O(lgn)）

我知道肯定有人是来找LCS最长公共子序列的模板的，直接给你，稍微改一下字符数组等等的就好了，我已经包装成一个函数了。

int lcs(int a[],int alength,int b[],int blength) {  
	for(int i=0;i<=alength;i++){
		dp[i][0]=0;
	}
	for(int i=0;i<=blength;i++){
		dp[0][i]=0;
	}
	for(int i=1;i<=alength;i++){
		for(int j =1;j<=blength;j++){
			if(a[i]==b[j])
				dp[i][j]=dp[i-1][j]+1;
			else{
				dp[i][j]=max(dp[i][j-1],dp[i-1][j]);
			}
		}
	}    
    return dp[alength][blength];  // 返回数组的指针  
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

洛谷P1439陷阱题啊！

我真傻，真的。我单知道雪天是野兽在深山里没有食吃，会到村里来；我不知道春天也会有……

鲁迅《祝福》祥林嫂

想仿照祥林嫂的话说一句：我真傻，真的。我单知道最长公共子序列，我不知道还有全排列啊！
这道题是真的坏，说是最长公共子序列的模板题，那就模板，不要再搞一个全排列又卡模板的O(n²)。让我单纯的上当了

但是我最后也是排除万难，发现了规律，AC！

#include
using namespace std;

int a[1007][1007]={0},num[27]={0},path[27]={0},f[27]={0};
 
int main(){
	int n,maxx=0,ans=0,now=0;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>num[i];
	}
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			cin>>a[i][j];	
		}	
	}
	f[n]=num[n];
	for(int i=n-1;i>0;i--){
		maxx=0;//maxx需要更新 
		for(int j=i+1;j<=n;j++){//获得可行域最大值 
			if(a[i][j])
				if(f[j]>f[maxx])
					maxx=j;
		}
		path[i]=maxx;//记录路径 
		f[i]=f[maxx]+num[i];//动态规划方程 
	} 
	//找到f[]中的最大值 
	for(int i=1;i<=n;i++){	
		if(f[i]>f[ans])
			ans=i; 
	}
	now=ans;
	while(path[now]){//等于0说明结束了，末尾没有其他路径了
		cout<<now<<" "; 
		now=path[now]; 
	}
	cout<<now<<endl;
	cout<<f[ans]<<endl;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

后话

王婆卖瓜

感觉有收获或者想跟上我的进度刷题的，可以点个关注，或者点赞收藏评论都可以！

题目来源

洛谷链接