洛谷 P1439 【模板】最长公共子序列
题目描述
给出1,2,…,n 的两个排列 P1? 和 P2? ,求它们的最长公共子序列。
输入格式
第一行是一个数 n。
接下来两行,每行为 n 个数,为自然数1,2,…,n 的一个排列。
输出格式
一个数,即最长公共子序列的长度。
输入输出样例
输入 #15 3 2 1 4 5 1 2 3 4 5输出 #1
3
说明/提示
- 对于 50% 的数据, n≤10^3;
- 对于 100% 的数据, n≤10^5。
引用一下阮行止dalao的题解:
为什么可以转化成LCS问题呢?
A:3 2 1 4 5
B:1 2 3 4 5
我们不妨给它们重新标个号:把3标成a,把2标成b,把1标成c……于是变成:
A: a b c d e
B: c b a d e
这样标号之后,LCS长度显然不会改变。但是出现了一个性质:
两个序列的子序列,一定是A的子序列。而A本身就是单调递增的。
因此这个子序列是单调递增的。
换句话说,只要这个子序列在B中单调递增,它就是A的子序列。
哪个最长呢?当然是B的LCS最长。
自此完成转化。
裸的dp时间复杂度是n^2的,跑不了。有一个优化成nlongn的方法。
我们另起一个数组end,end[ ltp ] (end 目前的最后一项) 为从n1到ni,最大上升子序列的结尾。
这就有了如下可意会的性质:
1)ltp最终的大小就是n数列的LCS项数。
2)如果n_i+1 > end[ ltp ],那么 end[ ++ltp ] = n_i+1;
3)如果n_i+1 < end[ ltp ],那么可以让 end [ pos ] = n_i+1。其中,pos = lower_bound( n_i+1 ) ( 这地方用low还是upp得具体分析。这题都可以。)这样的变化不 会影响ltp的大小,也不会影响最终答案。因为改变答案的修改是关于end最后一位的,而对end的修改必然是从左到右的,这顺序和n数列顺序是一致的。(这块先意会一下。如果日后我悟得更透彻了,话说得更明白了再来填一下坑)
这样一来,时间复杂度优化到nlogn。
#include二分优化求LCS#include #include #include using namespace std; int discre[100005],n[100005]; int end[100005]; int ltp=1; int read() { int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=x*10+ch-'0'; ch=getchar(); } return x*f; } int main() { int pos; int a=read(); for(int i=1;i<=a;i++) discre[read()]=i; for(int i=1;i<=a;i++) { n[i]=read(); n[i]=discre[n[i]]; } end[1]=n[1]; for(int i=2;i<=a;i++) { if(n[i]>end[ltp]) end[++ltp]=n[i]; else { pos=lower_bound(end+1,end+ltp+1,n[i])-end; end[pos]=n[i]; } } cout<<ltp; return 0; }