又是模板题呵，但这次的难度有点增加。
先看题目第一个想到DP的经典算法，要O(n^2)，然后想其它的算法。
其实我们衢州市一次联考有一题很像这题，不过还要难一点。
思想是离散化+最长不下降子序列（在这里和最长上升子序列等价，因为没有重复的值）
先离散一下第二串里每个点的第一串里的位置（数组也可以，但我喜欢用map），如样例：
5
3 2 1 4 5
1 2 3 4 5
散出来就是 3 2 1 4 5，然后为了使他们公共最长，想到什么？
最长不下降子序列！为什么？
刚开始做的是根据他们的数值，但现在将他们转化成了标号（important）
对于第一串的标号，很简单，就是1~n（自己对应自己的位置）
然后剩下的就是在第二串里找最长的递增作为它的重复部分了。
如果裸的最长不下降子序列（DP），复杂度也是O（n^2），贴一下代码，但道理应该大多数OI的书上都有
50CODE
#include<cstdio>
#include<map>
using namespace std;
inline void read(int &x)
{
x=; char ch=getchar();
while (ch<''||ch>'') ch=getchar();
while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();
}
inline int max(int a,int b) { return a>b?a:b; }
const int N=;
map <int,int> ma;
int n,x,num[N],f[N],ans,i,j;
int main()
{
read(n);
for (i=;i<=n;++i)
read(x),ma[x]=i;
for (i=;i<=n;++i)
read(x),num[i]=ma[x];
for (i=;i<=n;++i)
{
f[i]=;
for (j=;j<i;++j)
if (num[j]<num[i]) f[i]=max(f[i],f[j]+),ans=max(ans,f[i]);
}
printf("%d",ans);
return ;
}
然后优化。方法有两种——二分或树状数组。
个人还是感觉二分的简单些（因为不会打树状数组的版本）
用top表示最长不下降子序列的长度；表示用f[i]表示i长度的结尾元素的值。
仔细观察一下，发现他们满足f[1]<=f[2]<=f[3]……
然后就可以进行二分优化了
CODE（常数还挺小）
#include<cstdio>
#include<map>
using namespace std;
const int N=;
map <int,int> ma;
int n,x,num[N],f[N],i,top;
inline void read(int &x)
{
x=; char ch=getchar();
while (ch<''||ch>'') ch=getchar();
while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();
}
inline int max(int a,int b) { return a>b?a:b; }
inline int find(int x)
{
int left=,right=top,res=;
while (left<=right)
{
int mid=left+right>>;
if (f[mid]<x) res=mid,left=mid+; else right=mid-;
}
return res;
}
int main()
{
read(n);
for (i=;i<=n;++i)
read(x),ma[x]=i;
for (i=;i<=n;++i)
read(x),num[i]=ma[x];
for (i=;i<=n;++i)
{
if (!top) { f[++top]=num[i]; continue; } else
{
if (num[i]<f[]) f[]=num[i];
int k=find(num[i]);
top=max(top,k+);
f[k+]=num[i];
}
}
printf("%d",top);
return ;
}