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

heey

2017-11-08 09:34:56

Solution

看了看其他人写的题解,感觉有点冗杂,我想以最简单,通俗得写一下自己的理解,希望大家能得到我的帮助! 首先看到这道题很容易一下就想到dp(n^2),但是看看数据范围,放弃dp,再看一看它题目给出的,这两串数都是1到n的全排列,说白了就上下两个串中的元素都是相同的,只有顺序不同而已,那么知道这个,我们又怎么来解决这道题呢? 我们可以以第一个串为标准,用第二个串来匹配第一个串,看能匹配多少,所以,其实第一个串的每个数字其实影响不大,只有知道它对应了第二串的哪个数字就好了,那么我们为什么不把他给的串重新定义一下? 比如他的样例:3 2 1 4 5 我们把他变成 1 2 3 4 5 用一个数组记录一下每个数字变成了什么,相当于离散化了一下3-1;2-2;1-3;4-4;5-5; 现在我们的第二串1 2 3 4 5 按我们离散化的表示:3 2 1 4 5 可能有些人已经懂了,我们把第一个串离散化后的数组是满足上升,反过来,满足上升的也就是满足原串的排列顺序的,(如果你不懂的话可以多看几遍这个例子)O(∩\_∩)O~ 好了 ,现在的问题就变成了求一个最长不下降序列!好了!解决完成! ```cpp #include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std; int n; int a1[100010],a2[100010]; int belong[100010]; int f[100010],b[100010],len; int main() { freopen("a.in","r",stdin); scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&a1[i]); belong[a1[i]]=i; } for(int i=1;i<=n;i++) scanf("%d",&a2[i]); for(int i=1;i<=n;i++) { if(belong[a2[i]]>b[len]) { b[++len]=belong[a2[i]]; f[i]=len; continue; } int k=lower_bound(b+1,b+len+1,belong[a2[i]])-b; b[k]=belong[a2[i]]; f[i]=k; } printf("%d\n",len); return 0; } ```