P1439 【模板】最长公共子序列
题目链接-P1439 【模板】最长公共子序列
解题思路
- 首先根据概念,最长公共子序列,就是两段所含数字完全一样且顺序也一样的序列
- 我们可以将序列离散化,使,比如: {} {},我们可以给编号为: a b c d e,那么: c b a d e,{},按照数组映射后{}
- 这样我们就把问题转换成了求和的最长上升子序列,因为数据范围比较大,朴素法肯定会超时,我们可以用二分法求最长上升子序列
- 其实运用了贪心的思想:是上升子序列长度为的上升子序列的最小末尾数值,显然递增子序列末尾元素越小,后面的元素就越容易加入该上升子序列中
- 即每遇到一个新的元素时,就跟已经记录的数组当前所记录的最长升子序列的末尾元素相比较,如果大于此元素,就填到末尾元素的下一个,否则就不断向前找,直到找到一个刚好比它大的元素并替换
- 具体操作见代码
附上代码
#pragma GCC optimize("-Ofast","-funroll-all-loops") #include<bits/stdc++.h> #define int long long #define lowbit(x) (x &(-x)) #define endl 'n' using namespace std; const int INF=0x3f3f3f3f; const int dir[4][2]={-1,0,1,0,0,-1,0,1}; const double PI=acos(-1.0); const double e=exp(1.0); const double eps=1e-10; const int M=1e9+7; const int N=2e5+10; typedef long long ll; typedef pair<int,int> PII; typedef unsigned long long ull; int b[N],low[N],pos[N]; signed main(){ ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); int n,tmp,l=0; cin>>n; for(int i=1;i<=n;i++){ cin>>tmp; pos[tmp]=i; } for(int i=1;i<=n;i++){ cin>>tmp; b[i]=pos[tmp]; if(b[i]>low[l])//如果第i个数大于low数组的最大的数 low[++l]=b[i];//直接接在low数组的后面 else//如果第i个数不大于low数组中最大的数 low[lower_bound(low+1,low+1+l,b[i])-low]=b[i]; //那么就二分查找low中第一个小于等于b[i]的元素的位置,替换 } cout<<l<<endl; return 0; }
c/c++开发分享洛谷P1439 【模板】最长公共子序列地址:https://blog.csdn.net/Fiveneves/article/details/107241706
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/599458.html