最长公共子序列

一、什么是最长公共子序列(Longest Common Subsequence, LCS)?

最长公共子序列(LCS)是指在两个序列中，找出一个最长的子序列，使得这个子序列在这两个序列中都出现过。换句话说，就是从两个序列中删除一些元素后，剩下的最长公共子序列的长度。

二、原理

我们可以使用动态规划的方法来解决这个问题。首先，我们需要定义一个二维数组dp,其中dp[i][j]表示序列1的前i个元素和序列2的前j个元素的最长公共子序列的长度。接下来，我们可以通过以下步骤计算dp数组：

初始化dp数组的第一行和第一列为0。
从第二行第二列开始遍历dp数组，对于每个位置(i, j),如果序列1的第i个元素等于序列2的第j个元素，那么
```
\[dp[i][j] = dp[i-1][j-1] + 1 \]
 

否则，

 

\[dp[i][j] = max(dp[i-1][j], dp[i][j-1]) \]
 
```
最后，dp[m][n]就是我们要求的最长公共子序列的长度，其中m和n分别是序列1和序列2的长度。

三、C++代码实现

#include<bits/stdc++.h>
#define reg register
using namespace std;

// 定义一个函数read,用于读取输入的整数并返回
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1; // 如果输入的是负号，则将f设为-1
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48); // 将输入的数字转换为二进制表示，并存储在x中
        ch=getchar();
    }
    return x*f; // 返回读取的整数
}

// 定义一个函数write,用于输出整数x并在前面添加负号(如果x为负数)
void write(int x){
    if(x<0){
        putchar('-'); // 如果x为负数，先输出负号
        x=-x; // 将x变为正数
    }
    if(x>9) write(x/10); // 如果x大于9,递归调用write函数输出十位数
    putchar(x%10+'0'); // 输出个位数
    return ;
}

const int MAXN=100005,INF=0x7fffffff; // 定义常量MAXN为100005
int n,mapp[MAXN],dp[MAXN]; // 定义变量n、mapp[]、dp[]
vector<int > a,b; // 定义向量a、b

int main(){
    n=read(); // 从输入中读取整数n,存入变量n中
    a.push_back(0),b.push_back(0); // 在向量a和b的末尾分别添加元素0
    for(reg int i=1;i<=n;i++){a.push_back(read());mapp[a[i]]=i;} // 从输入中读取n个整数，存入向量a中，并将每个元素在向量a中的下标存入数组mapp中对应的位置
    for(reg int i=1;i<=n;i++){b.push_back(read());dp[i]=INF;} // 从输入中读取n个整数，存入向量b中，并将每个元素在dp[]中的值初始化为最大值
    for(reg int i=1;i<=n;i++) b[i]=mapp[b[i]]; // 将向量b中的每个元素替换为其在数组mapp中的下标所对应的值
    dp[1]=b[1]; // 将dp[1]设置为b[1]的值
    int len=1; // 将len设置为1
    for(reg int i=2;i<=n;i++){ // 从第2个元素开始遍历向量b和dp[]
        int l=0,r=len,mid; // 将l、r、mid分别初始化为0、len、len/2的商
        if(b[i]>dp[len]) dp[++len]=b[i]; // 如果b[i]大于dp[len],则将dp[len]更新为b[i]的值，并将len加1
        else{
            while(l<r){ // 当l小于r时，执行循环体
                mid=(l+r)>>1; // 将mid设置为l和r的平均值
                if(dp[mid]>b[i]) r=mid; // 如果dp[mid]大于b[i],则将r更新为mid的值
                else l=mid+1; // 否则将l更新为mid+1的值
            }
            dp[l]=min(b[i],dp[l]); // 将dp[l]更新为b[i]和dp[l]中的较小值
        }
    }
    write(len); // 将len写入输出流
    return 0; // 程序正常结束，返回0
}