华师一附中OI组

标题: P1439 【模板】最长公共子序列 [打印本页]
作者: universehyf    时间: 2018-10-15 21:37
标题: P1439 【模板】最长公共子序列
题目描述
给出1-n的两个排列P1和P2，求它们的最长公共子序列。
输入输出格式输入格式：

第一行是一个数n，
接下来两行，每行为n个数，为自然数1-n的一个排列。

输出格式：

一个数，即最长公共子序列的长度

输入输出样例输入样例#1：
[size=1.2][url=]复制[/url]
5 3 2 1 4 51 2 3 4 5
输出样例#1：
[size=1.2][url=]复制[/url]
3

说明
【数据规模】
对于50%的数据，n≤1000
对于100%的数据，n≤100000

作者: universehyf    时间: 2018-10-15 21:39
感谢蒋巨佬的思路
  1. #include<iostream>
  2. #include<string>
  3. using namespace std;
  4. #define FOR(i,n,m) for(int i=n;i<=m;i++)
  5. const int MAXN=100010;
  6. int n,a[MAXN],b[MAXN],mp[MAXN],f[MAXN],ans,l,r,mid;
  7. int main()
  8. {
  9.     cin>>n;FOR(i,1,n) cin>>a[i];FOR(i,1,n) cin>>b[i];
  10.     FOR(i,1,n) mp[a[i]]=i;f[0]=0;
  11.     FOR(i,1,n)
  12.     {
  13.         if(mp[b[i]]>f[ans]) f[++ans]=mp[b[i]];
  14.         else{
  15.             l=0;r=ans;
  16.             while(l<r)
  17.             {
  18.                 mid=l+(r-l)/2;
  19.                 if(mp[b[i]]>=f[mid]) l=mid+1;
  20.                 else r=mid;
  21.             }
  22.         }f[l]=min(mp[b[i]],f[l]);
  23.     }cout<<ans;
  24.     return 0;
  25. }
复制代码




欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2