我简直太爱 【模板】最长公共子序列

#include<bits/stdc++.h>
using namespace std;
int n,a[100010],b[100010],ans;
int f[100010],mp[100010];
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=n;i++) scanf("%d",&b[i]);
	for(int i=1;i<=n;i++)
	{
		f[i]=1e9;
		mp[a[i]]=i;
	}
	for(int i=1;i<=n;i++)
	{
		int l=0,r=ans,mid;
		if(mp[b[i]]>f[ans]) f[++ans]=mp[b[i]];
		else {
			while(l<r)
			{
				mid=(l+r)/2;
				if(f[mid]>mp[b[i]])r=mid;
				else l=mid+1;
			}
			f[l]=min(mp[b[i]],f[l]);
		}
	}
	printf("%d",ans);
	return 0;
}

 

可以暂时地把序列A( 3,1,2,5,4 )看作abcde,那么abc.....表示了数组A,只需要把B同步转换,按字典序查找最长上升子序列即可;

那么实现就好办了:mp[i]记录了一个值为 i 的数在A中出现的位置,搜索mp的上升序列——那么反过来,满足上升的B也就是满足A排列顺序的!!!

在查找上升子序列时,每一组子序列只需单点修改最大值,而每一组末值又是单调递增的,于是可以用二分法查找,插入要修改的最大值

推荐这些文章:

二分模板

#include<iostream> using namespace std; const int N=100010; int n,m; int q[N]; int main(){ scanf("%d%d",&n,&m); for(int i=0;i<n;i++) scanf("%d",&q[i]); while(m--){ int x; scanf("%d",&x); int l=0,r=n-1; while(l<r){ ...

整数二分查找模板

工具:VS2022
前提是一一个单调数组

#include<iostream>
using namespace std;
const int N = 1e6+10;
int n,m;
int q[N];
int main()
{
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)scanf("%d",&q[i]);
while(m--)
{
int x;
scanf("%d",&x);
int le=0,r=n-1;
while(le<r)
{
int mid=(le+r)>>1;
if(...

双指针算法模板

#include<iostream> using namespace std; const int N=100010; int q[N],s[N]; int main(){ int n; cin>>n; for(int i=0;i<n;i++) cin>>q[i]; int res=0; for(int i=0,j=0;i<n;i++){ s[q[i]]++; while(j<i && s[q[i]]>1) s[q[j++]]--; ...

归并排序模板

归并排序

#include<iostream>
using namespace std;
const int N =1e6+10;
int n;
int q[N];
int tmp[N];
void merge_sort(int q[],int le ,int r)
{
if(le>=r)return;
int mid=(le+r)>>1;
merge_sort(q,le,mid);
merge_sort(q,mid+1,r);
int k=0,i=le,j=mid+1;
while(i<=mid&&j<=r)
if(q[i]&l...

前缀和与差分模板(互逆运算)

序列和 #include<iostream> using namespace std; const int N=100010; int a[N],b[N]; int main(){ int n,m,l,r; cin>>n>>m; for(int i=1;i<=n;i++) cin>>b[i]; for(int i=1;i<=n;i++) a[i]=a[i-1]+b[i]; while(m--){ cin>>l>>r; ...

【模板】线性DP

#include<bits/stdc++.h>
using namespace std;
const int z = 1024;
int LIS(int *data) {
int ans = 1, linedp[z];
memset(linedp,0x7f,(data[0]+1)*sizeof(int));
linedp[1] = data[1];
for(int i = 2;i <= data[0];++i) {
if(data[i] > linedp[ans])
linedp[++ans] = data[i]...

最长公共子序列(模板题)

1.今天学了一手最长上升子序(模板题)
 
贴一下代码吧(输出最大路径值与输出路径

#include<bits/stdc++.h>
using namespace std;
int a[1010];
int p[1010];//p数组是记录路径下标
int f[1010];
int n;
void print(int i){//这里是输出路径,递推式,sum值逐渐递减
if(p[i]) print(p[i]);
printf("%d ",a[i]);
}
int main(){
cin>>n;
for(int i=1;i&l...

P5829 【模板】失配树 border

思路:
考虑对字符串\(s\)来说,假设\(s' = s_{1...x}\)是字符串的一个\(border\),同时\(s'' = s'_{1...y}\)是\(s'\)的一个border,那么\(s''\)也一定是\(s\)的一个长度更小的\(border\),即字符串\(s\)的\(border\)的\(border\)也是\(s\)的一个\(border\)。
这样我们就可从小遍历让每个位置\(i\)的\(border_i\)都连一条指向\(i\)的边,这样我们就可以构造出一棵\(border\)树,满足对于任意一个节点一定处在它的任何一个\(border\)的子树中。
考虑如何构建...

并查集模板 (洛谷p3367题解)

 
 
#include<bits/stdc++.h>using namespace std;const int maxn = 10005;int s[maxn];void init(){ // 初始化使初始的每个结点都是自己的根结点 for(int i = 1 ; i <= maxn ; i++){ s[i]=i; } }int find_set(int x){ // 找到每个元素的根结点,并且压缩路径使得每个元素直接接在根节点上 return x==s[x]?x:s[x]=find_set(s[x]);}void union_set(int...

AcWing 897. 最长公共子序列

题目链接

题目描述
给定两个长度分别为 N 和 M 的字符串 A 和 B,求既是 A 的子序列又是 B 的子序列的字符串长度最长是多少。
题目模型

集合表示:f(i,j)
集合含义:所有在第一个序列的前i个字母中出现,且在第二个序列的前j个字母中出现的子序列
集合属性:max
集合划分:

题目代码
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, m;
char a[N], b...

文章标题:我简直太爱 【模板】最长公共子序列
文章链接:https://www.dianjilingqu.com/51549.html
本文章来源于网络,版权归原作者所有,如果本站文章侵犯了您的权益,请联系我们删除,联系邮箱:saisai#email.cn,感谢支持理解。
THE END
< <上一篇
下一篇>>