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

 1、朴素做法

朴素的最长公共子序列(LCS)做法利用dp求解，定义dp[i][j]为只取序列a前i个数字与序列b前j个数字的最长公共子序列。对于dp[i][j]有4中情况：1.a[i]与b[j]都在LCS中。2.a[i]在LCS中，b[j]不在LCS中3.a[i]不在LCS中，b[j]不在LCS中。4.a[i]与B[j]都不在LCS中。

如果a[i]==b[j]则dp[i][j]为第一种情况，dp[i][j]==d[i-1][j-1]+1;如果a[i]=b[j],则为后三种情况，第二种情况dp[i][j]=dp[i][j-1],第三种情况dp[i-1][j]。第四种情况包含在第二三种情况的并集中。

所以状态转移方程为

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int dp[N][N],a[N],b[N];
int main()
{
	int n;
	cin>>n;
    for(int i=1;i<=n;i++)
    cin>>a[i];
    for(int i=1;i<=n;i++)
    cin>>b[i];
    for(int i=1;i<=n;i++)
    {
    	for(int j=1;j<=n;j++)
    	{
    		if(a[i]==b[j])
    		dp[i][j]=dp[i-1][j-1]+1;
    		else
    		dp[i][j]=max(dp[i][j-1],dp[i-1][j]); 
    	}
    }
    cout<<dp[n][n];
}

 但这道题的n高达1e5，朴素做法无论时间还是数组都不够用，但两序列长度相同并且都是1-n的排列，因此可以进行优化将时间复杂度降为nlogn，数组降为1维。

2.优化做法

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int a[N],b[N],c[N],f[N];
int len=1;
int main()
{
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
	scanf("%d",&a[i]);
	c[a[i]]=i;
    }
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&b[i]);
		b[i]=c[b[i]];
	}
	f[1]=b[1];
	for(int i=2;i<=n;i++)
	{
		if(f[len]<b[i])
		f[++len]=b[i];
		else
		f[lower_bound(f+1,f+len+1,b[i])-f]=b[i];
	}
	printf("%d",len);
}

利用f[i]存长度为i的最长公共子序列最后一个元素的位置。

把序列二映射为b[i]在a中的位置，比如a为2 1 3 5 4,b为3 2 1 4 5,则b[1]改为3，即b[1](3)在a中的位置。并且记录每一个长度的公共子序列最后一个元素在a中的位置，因为我们从左到右遍历b数组，如果b中存的当前元素在a的位置比当前保存的最长公共子序列的最后一个元素还要靠后，则最长公共子序列的长度+1，如果不是的话，肯定有某一长度的公共子序列的最后一个元素位置比遍历的位置大，则用当前遍历的位置来代替这一长度的最后一个元素位置，这是一种贪心做法。

 因为是从b数组从左往右遍历，所以后面遍历的位置一定在b数组是靠后的，而且b映射的是a中的位置，如图遍历到3的时候f[2]=4，遍历到2的时候发现2在a中的位置更靠前，所以更新f[2]=2,再遍历到4的时候更新f[3]=3，如果不把f[2]更新为更靠前的位置，那么则不能把f[3]更新为3。