每日一题 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 ;
}

请各位大佬斧正(反正我不认识斧正是什么意思)

最新文章

  1. 微信开发 企业号(二)-- 回调模式之Tooken验证 .net/python
  2. Cross-Entropy Loss 与Accuracy的数值关系
  3. 2014年4月份第4周51Aspx源码发布详情
  4. 锋利的jQuery-2--判断jQuery获取到的对象是否存在$().length
  5. javascript权威指南笔记--javascript语言核心(四)
  6. 防止双击选中html中文字
  7. Grails的redirect无法跳转时的一个可能原因
  8. mysql的面试试题
  9. C#高效导出Excel(IList转DataTable,DataSet)
  10. android listen
  11. UVa 496 - Simply Subsets
  12. C语言-for循环
  13. PHP的面向对象 — 封装、继承、多态
  14. 9.5、Libgdx加速度计
  15. SpringBoot 同时整合thymeleaf html、vue html和jsp
  16. 微信内无法自动跳转外部浏览器打开H5分享链接的解决办法
  17. 20175209 《Java程序设计》第六周学习总结
  18. 10_27_requests模块
  19. ArcGIS Construction Tool OnSketchFinished事件不响应
  20. Netty实战三之Netty的组件和设计

热门文章

  1. Win32API文本处理
  2. 【Linux】一步一步学Linux——Centos7.5安装图解(08)
  3. linux安装go开发环境
  4. golang方法和函数的区别
  5. html2canvas以及domtoimage的使用踩坑总结 动态获取的二维码失效如何生成海报
  6. 最清晰易懂的Mysql CURRENT_TIMESTAMP和ON UPDATE CURRENT_TIMESTAMP区别
  7. Abp session和Cookie
  8. Java序列化流
  9. iOS - WWDC18 iOS 自动生成强密码和自动填充验证码/密码
  10. Jboss部署war以及获取Resource的真实路径