See LCS again

本文主要是介绍See LCS again，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

描述

There are A, B two sequences, the number of elements in the sequence is n、m;

Each element in the sequence are different and less than 100000.

Calculate the length of the longest common subsequence of A and B.

输入

The input has multicases.Each test case consists of three lines;
The first line consist two integers n, m (1 < = n, m < = 100000);
The second line with n integers, expressed sequence A;
The third line with m integers, expressed sequence B;

输出

For each set of test cases, output the length of the longest common subsequence of A and B, in a single line.

样例输入

5 4
1 2 6 5 4
1 3 5 4

样例输出

3

上传者

TC_胡仁东

这个题关键是将LCS问题转化为最长上升子序列问题 （算法时间复杂度nlogn的方法）二分查找 详细见另一篇博客

AC代码如下：

#include<iostream>
#include<string.h>
#define N 100001
using namespace std;
int D[N];
int a[N],b[N];
int binarysearch(int low,int high,int m)//二分查找法
{int mid;mid=(low+high)/2;while(low<=high){if(D[mid]<m&&D[mid+1]>=m) return mid;else if(D[mid]<m)low=mid+1;else high=mid-1;mid=(low+high)/2;}  return mid;
}    
int main()
{int n,m;int i,j;int x;while(cin>>n>>m){memset(a,0,sizeof(a));memset(b,0,sizeof(b));for(i=1;i<=n;i++)//按顺序记录a串中各字符的位置{cin>>x;a[x]=i;}j=1;for(i=1;i<=m;i++){cin>>x;if(a[x])         //只保存a,b串公有字符b[j++]=a[x];//将问题转化成了最长递增子序列a[x]是x在a串的位置}int k,len;//memset(D,0,sizeof(D));D[1]=b[1];len=1;n=j-1;for(i=2;i<=n;i++){if(b[i]>D[len]){len++;D[len]=b[i];}else{j=binarysearch(1,len,b[i]);k=j+1;D[k]=b[i];}  }   cout<<len<<endl;  }return 0;
}

这篇关于See LCS again的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---