首页 > 其他分享 >P1439 【模板】最长公共子序列

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

时间:2024-09-11 19:24:22浏览次数:13  
标签:10 int st P1439 公共 序列 最长 模板

link

【模板】最长公共子序列

题目描述

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

输入格式

第一行是一个数 $n$。

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

输出格式

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

样例 #1

样例输入 #1

5 
3 2 1 4 5
1 2 3 4 5

样例输出 #1

3

提示

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

算法1

(LCS -> LIS) $O(n*logn)$

注意点:

看数据范围 $n \le 10^5$ 用朴素的LCS** $O(n^2)$**,肯定会超时;

想办法优化一下,我们直到最长上升子序列有一个二分优化版本: $O(nlogn)$

那么如何把最长公共子序列问题转化为最长上升子序列问题呢?

1.首先由题意可知,每行是已$1- n$组成的排列,说明两个数组中出现的元素是相同的,只是元素所在的位置不同

2.特性:最长公共子序列不是唯一的,但最长公共子序列的长度是唯一的

3.那么我们利用这一点,用st[]数组存放,a序列当中每个元素在b序列中出现的顺序,求b的最长LIS

看样例分析


a[]  : 3 2 1 4 5
b[]  : 1 2 3 4 5

st_a : 1 2 3 4 5
st_b : 3 2 1 4 5 

b中的最长上升子序列 : 1 4 5 

已知a数组是单调递增的,因此在b序列中找到的子序列,一定是a的子序列,

保证当前f[]中存放的是上升子序列的最小结尾值的下标

C++ 代码

//O(nlongn)
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;

int n;
int a[N],b[N];
int st[N];  //再a序列当中出现的位置
int f[N];   //当前公共子序列中结尾下标最小的

int main() {
	scanf("%d",&n);
	for(int i = 1; i <= n; i++) {
		scanf("%d",&a[i]);
		st[a[i]] = i;
	}
	for(int i = 1; i <= n; i++) {
		scanf("%d",&b[i]);
	}
	int len = 0;   //一开始为空集

	for(int i = 1; i <= n; i++) {
		int l = 0, r = len;
		if(st[b[i]] > f[len]) f[++len] = st[b[i]];
		else {
			while(l < r) {
				int mid = l + r >> 1;
				if(f[mid] > st[b[i]])   //找第一个大于st[b[i]]的下标
					r = mid;
				else l = mid + 1;
			}
			f[l] = min(f[l],st[b[i]]);   //两者当中取较小的 
		}
	}
     printf("%d",len);
     return 0;
}


标签:10,int,st,P1439,公共,序列,最长,模板
From: https://www.cnblogs.com/ltphy-/p/18408798

相关文章

  • 代码随想录训练营day44|1143.最长公共子序列,1035.不相交的线, 53. 最大子序和,392.判
    1143.最长公共子序列这题并不要求连续子序列的要求是可以删除某些元素,但不能改变顺序。顺着上题的思路,这题也应该设立一个二维数组vector<vector<int>>dp(text1.size(),vector<int>(text2.size(),0));dp[i][j]表示的是以text1[i]为结尾的字符串和以text2[j]为结尾的......
  • Solidworks学习:在新建零件时总是提示「默认模板无效」的解决方案
    在我们打开Solidworks新建零件或装配体时,总是提示我们「默认模板无效」。然而,即便我们对其置之不理并继续创建,依然能够顺利完成,貌似此“默认模板无效”的提示对我们毫无影响。可若真无影响,那它又为何要显现这一提示呢?其实,这个默认模板的作用主要是新建文件的时候,让新建零件里......
  • 健身运动俱乐部主题网页设计制作 | html网页模板源码
    文章目录网站主题网站描述网站介绍网站演示学习理念更多干货一、网站主题健身网站、健身房网站、健身网页、健身房网页、健身网页、团操运动网页、健身俱乐部html网页、html健身运动主题网页、html网页设计与制作、学生期末网页大作业二、网站描述编码:A04、页数:6页,技术:h......
  • Springboot枚举自定义序列化
    packagexxxxxxxxxxxxx;importcom.fasterxml.jackson.core.JsonGenerator;importcom.fasterxml.jackson.databind.JsonSerializer;importcom.fasterxml.jackson.databind.ObjectMapper;importcom.fasterxml.jackson.databind.SerializerProvider;importcom.fasterx......
  • Vue模板语言入门
    一、绑定事件监听        接上集,如果想看vue基础请移步主页      1、默认事件形参event:            即在对象触发事件的函数的默认参数,即使在标签内触发函数位置没写event参数也可以在script函数中直接写:函数名(event){函......
  • 【生日视频制作】直升机飞机侧身AE模板修改文字软件生成器教程特效素材【AE模板】
    生日视频制作教程直升机飞机侧身AE模板修改文字特效广告生成神器素材祝福玩法AE模板工程AE模板套用改图文教程↓↓:怎么如何做的【生日视频制作】直升机飞机侧身AE模板修改文字软件生成器教程特效素材【AE模板】生日视频制作步骤:下载AE模板安装AE软件把AE模板导入......
  • 【高级编程】Java IO流(补)序列化 & 反序列化
    序列化(ObjectOutputStream)&反序列化(ObjectInputStream)Java的序列化和反序列化是用于将对象转换为字节流的过程,以便在网络上传输或保存到磁盘,然后将这些字节流再转换回对象。这个过程是Java中处理对象持久化和传输的常见方法。序列化是将对象的状态转换为字节流的过......
  • LeetCode: 673.最长子序列的数量 动态规划 时间复杂度O(n*n)
    673.最长子序列的数量LeetCode原题连接673.最长子序列的数量题目描述给定一个未排序的整数数组,找到最长递增子序列的个数。示例1:输入:[1,3,5,4,7]输出:2解释:有两个最长递增子序列,分别是[1,3,4,7]和[1,3,5,7]。示例2:输入:[2,2,2,2,2]输出:5......
  • 洛谷题单指南-分治与倍增-P1177 【模板】归并排序
    原题链接:https://www.luogu.com.cn/problem/P1177题意解读:归并排序模版题。解题思路:第一步:确定分界点。mid=(l+r)/2第二步:排序。对左右两边递归排序第三步:归并。合并左右两边排序好的内容关键在第三步:通过双指针对两个有序数组进行合并100分代码:#include<bits/std......
  • JAVA中的八大排序 可视化精华模板 (思路+代码实践)
    “批判他人总是想的太简单剖析自己总是想的太困难”文章目录前言文章有误敬请斧正不胜感恩!1.冒泡排序(时间复杂度o(n^2))概念步骤可视化代码实现2.选择排序(时间复杂度o(n^2))概念步骤可视化代码实现3.插入排序(时间复杂度o(n^2))概念步骤可视化代码示例4.快速排序(时间......