首页 > 代码库 > -----[DP] LCS小结
-----[DP] LCS小结
额、、失误、、
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 1010int p,q;int a[N];int b[N];int dp[N][N];void solve(){ int i,j; memset(dp,0,sizeof(dp)); for(i=1;i<=p;i++) { for(j=1;j<=q;j++) { if(a[i]==b[j]) { dp[i][j]=dp[i-1][j-1]+1; } else { dp[i][j]=max(dp[i-1][j],dp[i][j-1]); } } } cout<<dp[p][q]<<endl;}int main(){ int i; while(scanf("%d%d",&p,&q)!=EOF) { for(i=1;i<=p;i++) { scanf("%d",&a[i]); } for(i=1;i<=q;i++) { scanf("%d",&b[i]); } solve(); } return 0;}
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 1010int len;int p,q;int a[N];int b[N];int dp[N];void convert(){ int i,hash[N]={0}; for(i=1;i<=p;i++) { hash[a[i]]=i; } for(i=1;i<=q;i++) { b[i]=hash[b[i]]; }}int up_bound(int k){ int l=1,r=len+1; while(l<r) { int m=(l+r)>>1; if(dp[m]<=k) l=m+1; else r=m; } return l;}void solve(){ len=0; dp[0]=-0x7ffffff; for(int i=1;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=1;i<=p;i++) { scanf("%d",&a[i]); } for(int i=1;i<=q;i++) { scanf("%d",&b[i]); } convert(); solve(); } return 0;}
2、当有重复元素时：
#include <iostream>#include <cstdio>#include <vector>#include <cstring>using namespace std;#define N 10010int 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=1;i<=p;i++) { v[a[i]].push_back(i); } n=0; for(int i=1;i<=q;i++) { for(int j=v[b[i]].size()-1;j>=0;j--) { s[++n]=v[b[i]][j]; } }}int up_bound(int k){ int l=1,r=len+1; while(l<r) { int m=(l+r)>>1; if(dp[m]<=k) l=m+1; else r=m; } return l;}void solve(){ len=0; dp[0]=-0x7fffffff; for(int i=1;i<=n;i++) { if(s[i]>dp[len]) dp[++len]=s[i]; else { int pos=up_bound(s[i]-1); dp[pos]=s[i]; } } printf("%d\n",len);}int main(){ while(scanf("%d%d",&p,&q)!=EOF) { for(int i=1;i<=p;i++) { scanf("%d",&a[i]); } for(int i=1;i<=q;i++) { scanf("%d",&b[i]); } convert(); solve(); } return 0;}
-----[DP] LCS小结