【离散化+LIS】swjtuOJ 2091

【注：交大的看到这篇文章要学会自己写，不要为了比赛而比赛！~】

题目大意

给你两组n个数的序列，求他们最长公共序列（LCS）,n<=10^5

对第一组序列数字编号，再对第二组序列构造他们编号对应的序列s,求解序列s的最长上升子序列即可（LIS）

说一下思路这道题之前没做过，编号过程有人说是离散化，还不是很清楚，注意{a}序列中的数字可能在{b}序列不存在，要判断mp[a[i]]是否为空；LIS用O（NlogN）的算法，采用二分思想，这里顺便学习下了

数组a[]使用前要清空

参考代码;const int _max = 1e5 + 10;map<int,int>mp;int a[_max],b[_max],c,d,n;//用二分查找的方法找到一个位置，使得num>b[i-1]且num<b[i]，，并用num代替b[i]int bsearch(int num,int L,int R){ int mid; while(L <= R){mid = (L + R) >> 1;if( num >= b[mid]) L = mid + 1;else R = mid – 1; } return L;};//没有公共部分 int len = 1,pos; b[1] = a[1]; for(int i = 2; i <= n; ++ i){if(a[i]>=b[len]){//如果a[i]比b[]数组中最大还大，直接插入到后面即可len++;b[len] = a[i];}else{pos = bsearch(a[i],1,len);//用二分查找的方式在b[]数组中找出第一个比a[i]大……b[pos] = a[i];//的位置并且让a[i]替代这个位置} } return len;}int main(){ #ifndef ONLINE_JUDGE freopen(“input.txt”,”r”,stdin); #endif // ONLINE_JUDGE while(scanf(“%d”,&n)==1){mp.clear();clr(a,0); // clr(b,0);int top = 1;for(int i = 1; i <= n; ++ i){scanf(“%d”,&c);mp[c] = top++;//对序列a中的元素编号}top = 1;for(int i = 1; i <= n; ++ i){scanf(“%d”,&d);if(mp[d]) a[top++] = mp[d];//构造带LIS的序列a[],注意不一定有n个公共元素}printf(“%d\n”,DP(top)); } return 0;}

见过旅行风景，就这样，慢慢学会了长大。

相关文章：

你感兴趣的文章：

标签云：