看过好多人的博客, 感觉要么是太复杂要么就是太不容易理解.
那就亲自动手写一个通俗易懂的.
先定义两个数组, 第一个数组为主, 用第二个数组来匹配第一个, 看能有多少可以对应上的.
所以, 其实第一个数组的内容可以暂时不考虑, 当知道它对应了第二个数组的哪个数字就 BINGO 了.
顺着这个思路继续想就可以得到以下思路:
把第一个数组离散化 (记录第一个数组变成什么) 后的数组是满足上升的关系.
现在的问题就变成了求一个最长不下降序列.
二话不说上代码.
------------------------------------------ 一道华丽的分割线 ------------------------------------------
- #include<iostream>
- #include<cstdio>
- #include<cstdlib>
- #include<cstring>
- #include<algorithm>
- #include<cmath>
- #include<cctype>
- #define rg register
- #define int long long
- using namespace std;
- inline int read(){
- rg int s=0,f=0;
- rg char ch=getchar();
- while(!isdigit(ch)) f|=(ch=='-'),ch=getchar();
- while(isdigit(ch)) s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
- return f?-s:s;
- }
- int n,len;
- const int MAX=100010;
- int a1[MAX],a2[MAX],f[MAX],b[MAX],c[MAX];
- signed main(){
- n=read();
- for(rg int i=1;i<=n;++i){
- a1[i]=read();
- c[a1[i]]=i;
- }
- for(rg int i=1;i<=n;++i){
- a2[i]=read();
- }
- for(rg int i=1;i<=n;++i){
- if(c[a2[i]]>b[len]){
- b[++len]=c[a2[i]];
- f[i]=len;
- continue;
- }
- int k=lower_bound(b+1,b+len+1,c[a2[i]])-b;
- b[k]=c[a2[i]];
- f[i]=k;
- }
- printf("%d\n",len);
- return 0;
- }
[模板] 最长公共子序列(LCS).
来源: http://www.bubuko.com/infodetail-2876866.html