华师一附中OI组

 找回密码
 立即注册
搜索
热搜: 活动 交友 discuz
查看: 1002|回复: 1
打印 上一主题 下一主题

P1439 【模板】最长公共子序列

[复制链接]

14

主题

106

帖子

317

积分

中级会员

Rank: 3Rank: 3

积分
317
跳转到指定楼层
楼主
发表于 2018-10-15 21:37:35 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
题目描述
给出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

回复

使用道具 举报

14

主题

106

帖子

317

积分

中级会员

Rank: 3Rank: 3

积分
317
沙发
 楼主| 发表于 2018-10-15 21:39:00 | 只看该作者
感谢蒋巨佬的思路
  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. }
复制代码
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

QQ|Archiver|手机版|小黑屋|服务支持:DZ动力|华师一附中OI组  

GMT+8, 2024-12-26 02:06 , Processed in 0.330634 second(s), 23 queries .

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表