额、、失误、、
LCS是Longest Common Subsequence的缩写，即最长公共子序列。一个序列，如果是两个或多个已知序列的子序列，且是所有子序列中最长的，则为最长公共子序列。
DP、O(n^2)解法：
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define max(a,b) ((a)>(b)?(a):(b))
#define N 1010 int p,q;
int a[N];
int b[N];
int dp[N][N]; void solve()
{
int i,j;
memset(dp,,sizeof(dp));
for(i=;i<=p;i++)
{
for(j=;j<=q;j++)
{
if(a[i]==b[j])
{
dp[i][j]=dp[i-][j-]+;
}
else
{
dp[i][j]=max(dp[i-][j],dp[i][j-]);
}
}
}
cout<<dp[p][q]<<endl;
}
int main()
{
int i;
while(scanf("%d%d",&p,&q)!=EOF)
{
for(i=;i<=p;i++)
{
scanf("%d",&a[i]);
}
for(i=;i<=q;i++)
{
scanf("%d",&b[i]);
}
solve();
}
return ;
}
O（nlogn）解法：
参考：http://www.cs.ucf.edu/courses/cap5937/fall2004/Longest%20common%20subsequence.pdf
最长公共子序列 的 nlogn 的算法本质是 将该问题转化成 最长增序列（LIS），因为 LIS 可以用nlogn实现，所以求LCS的时间复杂度降低为 nlogn。
转化：将LCS问题转化成LIS问题。
假设有两个序列 s1[ 1~6 ] = { a, b, c , a, d, c }, s2[ 1~7 ] = { c, a, b, e, d, a, b }。
记录s1中每个元素在s2中出现的位置, 再将位置按降序排列, 则上面的例子可表示为：
loc( a）= { 6, 2 }, loc( b ) = { 7, 3 }, loc( c ) = { 1 }, loc( d ) = { 5 }。
将s1中每个元素的位置按s1中元素的顺序排列成一个序列s3 = { 6, 2, 7, 3, 1, 6, 2, 5, 1 }。
在对s3求LIS得到的值即为求LCS的答案。（这点我也只是大致理解，读者可以自己理解甚至证明。）
上面一段话转载自：http://blog.csdn.net/non_cease/article/details/6918848
1、当无重复元素时：
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define N 1010 int len;
int p,q;
int a[N];
int b[N];
int dp[N]; void convert()
{
int i,hash[N]={};
for(i=;i<=p;i++)
{
hash[a[i]]=i;
}
for(i=;i<=q;i++)
{
b[i]=hash[b[i]];
}
}
int up_bound(int k)
{
int l=,r=len+;
while(l<r)
{
int m=(l+r)>>;
if(dp[m]<=k) l=m+;
else r=m;
}
return l;
}
void solve()
{
len=;
dp[]=-0x7ffffff;
for(int i=;i<=q;i++)
{
if(!b[i]) continue;
if(b[i]>dp[len]) dp[++len]=b[i];
else
{
int pos=up_bound(b[i]);
dp[pos]=b[i];
}
}
printf("%d\n",len);
}
int main()
{
while(scanf("%d%d",&p,&q)!=EOF)
{
for(int i=;i<=p;i++)
{
scanf("%d",&a[i]);
}
for(int i=;i<=q;i++)
{
scanf("%d",&b[i]);
}
convert();
solve();
}
return ;
}
2、当有重复元素时：
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
#define N 10010 int n;
int p,q;
int len;
int a[N];
int b[N];
int s[N];
int dp[N]; void convert()
{
vector<int> v[N];
for(int i=;i<=p;i++)
{
v[a[i]].push_back(i);
}
n=;
for(int i=;i<=q;i++)
{
for(int j=v[b[i]].size()-;j>=;j--)
{
s[++n]=v[b[i]][j];
}
}
}
int up_bound(int k)
{
int l=,r=len+;
while(l<r)
{
int m=(l+r)>>;
if(dp[m]<=k) l=m+;
else r=m;
}
return l;
} void solve()
{
len=;
dp[]=-0x7fffffff;
for(int i=;i<=n;i++)
{
if(s[i]>dp[len]) dp[++len]=s[i];
else
{
int pos=up_bound(s[i]-);
dp[pos]=s[i];
}
}
printf("%d\n",len);
}
int main()
{
while(scanf("%d%d",&p,&q)!=EOF)
{
for(int i=;i<=p;i++)
{
scanf("%d",&a[i]);
}
for(int i=;i<=q;i++)
{
scanf("%d",&b[i]);
}
convert();
solve();
}
return ;
}