Luogu 3402 最长公共子序列（二分，最长递增子序列）

Description

经过长时间的摸索和练习，DJL终于学会了怎么求LCS。Johann感觉DJL孺子可教，就给他布置了一个课后作业：

给定两个长度分别为n和m的序列，序列中的每个元素都是正整数。保证每个序列中的各个元素互不相同。求这两个序列的最长公共子序列的长度。

DJL最讨厌重复劳动，所以不想做那些做过的题。于是他找你来帮他做作业。

Input

第一行两个整数n和m，表示两个数列的长度。 第二行一行n个整数\[a_1,a_2,…,a_n，保证1≤a_i≤10^9\]。 第三行一行m个整数\[b_1,b_2,…,b_m，保证1≤b_i≤10^9\]。

对于40%的数据，n, m≤3000 对于100%的数据，n, m≤300000

Output

一行一个整数，表示两个数列的最长公共子序列的长度。

Sample Input

6 6 1 3 5 7 9 8 3 4 5 6 7 8

Sample Output

4

Http

Luogu:https://www.luogu.org/problem/show?pid=3402

Source

二分

解决思路

这道题的弱化版在这里。

因为数据加强了，我们不能使用弱化版中的动态规划方法了。

题目中给出了元素互不相同的条件。我们可以将求最长公共子序列（LCS）转化为求最长递增子序列（LIS）。

读入A数组的时候，我们定义一个Map[x]表示数x对应的编号，Map[x]=i;这样就相当于把数组A变成了一个递增的序列。

如果我们把B数组里的数都按照A中的规则转置一下，这个题目就变成求B的最长递增子序列了，具体操作如下:

然后在处理B数组的时候（假设我们现在处理数字x），先让x=Map[x]如果此时x==0则说明原来的数字x并没有在数组A中出现过，所以自然也不会成为最长公共子序列的解，直接舍去即可。

这时我们将找到的最长递增子序列放入一个vector（这里用Arr表示），并保证其有序。若x（这个x是用Map转置后的）比vector里所有元素都大（即比Arr[Arr.size()-1]大），则直接将其放到队尾；否则二分查找第一个比x大的元素并替换之。

相信你也发现了，这个算法的核心思路是贪心，我们可以看到，它是让Arr中的元素尽可能的小，以此来求出最长递增子序列，也就可以求出原题的最长公共子序列。

需要注意的是，用这种算法求最长递增子序列只能求出其长度，Arr中的数不一定就是最后要求的最长递增子序列。（为什么呢？仔细想一想）

PS:这个题目真心坑爹，不仅要用上面的这个算法，读入还必须用getchar()读入优化，就连scanf都会超时，真是……

代码

#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> #include<vector> #include<map> using namespace std; int n,m; map<int,int> Map; vector<int> Arr; int read();//读入优化，一定要打 int main() { int x; n=read(); m=read(); for (int i=1;i<=n;i++) { //scanf("%d",&x); Map[read()]=i; } for (int i=1;i<=m;i++)//将LCS问题转换为LIS问题，降低时间复杂度 { //scanf("%d",&x); x=Map[read()]; if (x==0) continue; if ((Arr.size()==0)||(x>Arr[Arr.size()-1]))//如果比其中的都大，直接放到后面 Arr.push_back(x); else//否则，替换第一个比它大的 *lower_bound(Arr.begin(),Arr.end(),x)=x; } cout<<Arr.size()<<endl;//Arr的大小就是最后最长子序列的大小 return 0; } int read() { int x=0; int k=1; char ch=getchar(); while (((ch<'0')||(ch>'9')) &&(ch!='-')) ch=getchar(); if (ch=='-') { k=-1; ch=getchar(); } while ((ch<='9')&&(ch>='0')) { x=x*10+ch-48; ch=getchar(); } return x*k; }

转载于:https://www.cnblogs.com/SYCstudio/p/7137870.html