洛谷 P1439 【模板】最长公共子序列 题解
2024-08-22 11:42:39
每日一题 day40 打卡
Analysis
因为两个序列都是1~n 的全排列,那么两个序列元素互异且相同,也就是说只是位置不同罢了,那么我们通过一个book数组将A序列的数字在B序列中的位置表示出来
因为最长公共子序列是按位向后比对的,所以a序列每个元素在b序列中的位置如果递增,就说明b中的这个数在a中的这个数整体位置偏后,可以考虑纳入LCS——那么就可以转变成nlogn求用来记录新的位置的book数组中的LIS。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 100000+10
#define INF 9187201950435737471
#define rep(i,s,e) for(register int i=s;i<=e;++i)
#define dwn(i,s,e) for(register int i=s;i>=e;--i)
using namespace std;
inline int read()
{
int x=;
bool f=;
char c=getchar();
for(; !isdigit(c); c=getchar()) if(c=='-') f=;
for(; isdigit(c); c=getchar()) x=(x<<)+(x<<)+c-'';
if(f) return x;
return -x;
}
inline void write(int x)
{
if(x<){putchar('-');x=-x;}
if(x>)write(x/);
putchar(x%+'');
}
int n,ans=;
int a[maxn],b[maxn],book[maxn],last[maxn];
signed main()
{
n=read();
rep(i,,n) a[i]=read(),book[a[i]]=i;
rep(i,,n) b[i]=read();
last[]=book[b[]];
rep(i,,n)
{
if(book[b[i]]>=last[ans]) last[++ans]=book[b[i]];
else
{
int num=upper_bound(last+,last+ans+,book[b[i]])-last;
last[num]=book[b[i]];
}
}
write(ans);
return ;
}
请各位大佬斧正(反正我不认识斧正是什么意思)
最新文章
- 微信开发 企业号(二)-- 回调模式之Tooken验证 .net/python
- Cross-Entropy Loss 与Accuracy的数值关系
- 2014年4月份第4周51Aspx源码发布详情
- 锋利的jQuery-2--判断jQuery获取到的对象是否存在$().length
- javascript权威指南笔记--javascript语言核心(四)
- 防止双击选中html中文字
- Grails的redirect无法跳转时的一个可能原因
- mysql的面试试题
- C#高效导出Excel(IList转DataTable,DataSet)
- android listen
- UVa 496 - Simply Subsets
- C语言-for循环
- PHP的面向对象 — 封装、继承、多态
- 9.5、Libgdx加速度计
- SpringBoot 同时整合thymeleaf html、vue html和jsp
- 微信内无法自动跳转外部浏览器打开H5分享链接的解决办法
- 20175209 《Java程序设计》第六周学习总结
- 10_27_requests模块
- ArcGIS Construction Tool OnSketchFinished事件不响应
- Netty实战三之Netty的组件和设计
热门文章
- Win32API文本处理
- 【Linux】一步一步学Linux——Centos7.5安装图解(08)
- linux安装go开发环境
- golang方法和函数的区别
- html2canvas以及domtoimage的使用踩坑总结 动态获取的二维码失效如何生成海报
- 最清晰易懂的Mysql CURRENT_TIMESTAMP和ON UPDATE CURRENT_TIMESTAMP区别
- Abp session和Cookie
- Java序列化流
- iOS - WWDC18 iOS 自动生成强密码和自动填充验证码/密码
- Jboss部署war以及获取Resource的真实路径