目录

最长公共子序列（LCS）问题

给出两个⻓度为n的序列 { a i } 和 { b i } \{a_i\}和\{b_i\} {ai​}和{bi​}，求它们的公共子序列的最⻓⻓ 度。 例如两个序列分别为 ( 1 , 2 , 4 , 8 , 16 ) (1,2,4,8,16) (1,2,4,8,16)和 ( 2 , 4 , 6 , 8 , 10 ) (2,4,6,8,10) (2,4,6,8,10)，那么它们的 L C S LCS LCS就是 ( 2 , 4 , 8 ) (2,4,8) (2,4,8)。

由于子序列是按照从前往后的顺序，我们自然而然地可以将这两个序列 的前缀序列的LCS问题作为子问题。

1.朴素做法 O ( n 2 ) O(n^2) O(n2)

设 f ( i , j ) f(i,j) f(i,j) 为 a a a 序列的前 i i i个数字，和 b b b 序列的前 j j j 个数字，的 L C S LCS LCS。那 么分别考虑最后两个数字的情况：

▶ 如果相同，则加入 L C S LCS LCS中，并计算 f ( i − 1 , j − 1 ) ； f(i−1,j−1)； f(i−1,j−1)；

▶ 如果不同，则寻找退路，在 f ( i − 1 , j ) f(i−1,j) f(i−1,j)和 f ( i , j − 1 ) f(i,j−1) f(i,j−1)中取较大的。 复杂度 O ( n 2 ) O(n^2) O(n2)。

那么看一下这个模板题：

50%的数据 n < = 1 0 3 n<=10^3 n<=103

根据上面分析的朴素做法代码如下：

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
#include<math.h>
#include<vector>
#define ls (p<<1)
#define rs (p<<1|1)
#define mid (l+r)/2
#define over(i,s,t) for(register long long i=s;i<=t;++i)
#define lver(i,t,s) for(register long long i=t;i>=s;--i)
//#define int __int128
using namespace std;
typedef long long ll;//全用ll可能会MLE或者直接WA,试着改成int看会不会A
const ll N=100007;
const ll INF=1e10+9;
const ll mod=2147483647;
const double EPS=1e-10;//-10次方约等于趋近为0
const double Pi=3.1415926535897;
ll n,m,a[N],b[N],f[100005][10005];
void naive()//（太天真了）
{
    over(i,1,n)
    over(j,1,n)
    {
        if(a[i]==b[j])
            f[i][j]=f[i-1][j-1]+1;
        else f[i][j]=max(f[i-1][j],f[i][j-1]);
    }
    printf("%lld\n",f[n][n]);
}
int main()
{
    scanf("%lld",&n);
    over(i,1,n)
        scanf("%lld",&a[i]);
    over(i,1,n)
        scanf("%lld",&b[i]);
    naive();
    return 0;
}

果不其然过了50%的点，只拿了50分。

朴素做法还是太天真了，但是有一系列的题只要求你用朴素做法

要是想拿满分，就必须要优化到 O ( n l o g n ) O(nlogn) O(nlogn)才行

2.转换成LIS优化 O ( n l o g n ) O(nlogn) O(nlogn)

如果a和b都各自满足数字互不相同的性质，那么解法可以得到进一步优化。

首先将a和b中的数字进行离散化，并去除只在一个序列中出现的数 字。那么对于剩下的a中的每个数字，它在b中某个位置对应出现，于 是问题就变成了：选取尽可能多的a，使得它们在b中对应的出现顺序 单调递增。
也就是一个 L I S LIS LIS（最长上升子序列）问题。 从而可以在 O ( n l o g n ) O(nlogn) O(nlogn)的复杂度进行解决。

没看懂？没事，下面给出一个大佬的解释

关于为什么可以转化成 L I S LIS LIS问题

A : 32145 A:3 2 1 4 5 A:32145
B : 12345 B:1 2 3 4 5 B:12345
我们不妨给它们重新标个号：把3标成a,把2标成b，把1标成c……于是变成：
A : a b c d e A: a b c d e A:abcde
B : c b a d e B: c b a d e B:cbade
这样标号之后， L C S LCS LCS长度显然不会改变。但是出现了一个性质：
两个序列的子序列，一定是A的子序列。而A本身就是单调递增的。
因此这个子序列是单调递增的。
换句话说，只要这个子序列在B中单调递增，它就是A的子序列。
哪个最长呢？当然是B的 L I S LIS LIS最长。
自此完成转化。

很清晰对吧，那么我们就可以把LCS问题转换成LIS问题来用 O ( n l o g n ) O(nlogn) O(nlogn)求解了。什么，你还不会LIS（最长上升子序列）？快点开[这个链接学习一下
https://blog.csdn.net/weixin_45697774/article/details/105465483

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
#include<math.h>
#include<vector>
#define ls (p<<1)
#define rs (p<<1|1)
#define mid (l+r)/2
#define over(i,s,t) for(register long long i=s;i<=t;++i)
#define lver(i,t,s) for(register long long i=t;i>=s;--i)
//#define int __int128
using namespace std;
typedef long long ll;//全用ll可能会MLE或者直接WA,试着改成int看会不会A
const ll N=100007;
const ll INF=1e10+9;
const ll mod=2147483647;
const double EPS=1e-10;//-10次方约等于趋近为0
const double Pi=3.1415926535897;
ll n,m,a[N],b[N],tree[N],mp[N];

inline void update(ll k,ll val)//树状数组维护的是mp数组的值的最大值
{
    while(k<=N)
    {
        tree[k]=max(tree[k],val);
        k+=k&(-k);
    }
}
inline ll query(ll k)//查到的k都是值小于k的节点的最大值，所以就保证了单调性
{
    ll res=0;
    while(k)
    {
        res=max(res,tree[k]);
        k-=k&(-k);
    }
    return res;
}

void advanced()
{
    over(i,1,n)
        mp[b[i]]=i;//mp函数就是一个简单的映射离散化
    over(i,1,n)//如果a里有b里没有那么p[a[i]]就是0，树状数组是没办法处理0的所以就不会任何影响
        update(mp[a[i]],query(mp[a[i]])+1);
    printf("%lld\n",query(n));
}
int main()
{
    scanf("%lld",&n);
    over(i,1,n)
        scanf("%lld",&a[i]);
    over(i,1,n)
        scanf("%lld",&b[i]);
    advanced();
    return 0;
}

3.P2758 编辑距离

P2758 编辑距离

类似 L C S LCS LCS来定义状态：设f(i,j)表示 A [ 1... i ] 和 B [ 1... j ] A[1...i]和B[1...j] A[1...i]和B[1...j]的编辑距离。

由于编辑之后最后一个字符一定要相同，我们就分情况讨论：

▶ 如果 A [ i ] = B [ j ] A[i] = B[j] A[i]=B[j]，则 f ( i , j ) = f ( i − 1 , j − 1 ) f(i,j) = f(i−1,j−1) f(i,j)=f(i−1,j−1)

▶ 否则，我们有三种不同的操作方法：

  1. 将 A [ i ] A[i] A[i]删除，转化为 f ( i − 1 , j ) f(i−1,j) f(i−1,j)
  2. 将 B [ j ] B[j] B[j]插入到最后，转化为$f(i,j−1) $
  3. 将 A [ i ] A[i] A[i]修改为 B [ j ] B[j] B[j]，转化为 f ( i − 1 , j − 1 ) f(i−1,j−1) f(i−1,j−1)

注意边界条件： f ( 0 , i ) = f ( i , 0 ) = i f(0,i) = f(i,0) = i f(0,i)=f(i,0)=i

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
#include<math.h>
#include<vector>
#define ls (p<<1)
#define rs (p<<1|1)
#define mid (l+r)/2
#define over(i,s,t) for(register long long i=s;i<=t;++i)
#define lver(i,t,s) for(register long long i=t;i>=s;--i)
//#define int __int128
using namespace std;
typedef long long ll;//全用ll可能会MLE或者直接WA,试着改成int看会不会A
const ll N=2007;
const ll INF=1e10+9;
const ll mod=2147483647;
const double EPS=1e-10;//-10次方约等于趋近为0
const double Pi=3.1415926535897;
ll n,m,f[N][N];
char a[N],b[N];
int main()
{
    scanf("%s%s",a+1,b+1);
    n=strlen(a+1),m=strlen(b+1);
    over(i,1,N-1)//必须-1，f数组总共就从0-(N-1),就是搞不明白为什么这里写错答案会不一样
        f[0][i]=f[i][0]=i;
    over(i,1,n)over(j,1,m)
    {
        if(a[i]==b[j])
            f[i][j]=f[i-1][j-1];//不用改
        else f[i][j]=min(min(f[i-1][j]+1,//删掉a
                            f[i][j-1]+1),//删掉b
                          f[i-1][j-1]+1);//把a改成b
    }
    printf("%lld\n",f[n][m]);
}

注：如果您通过本文,有(qi)用(guai)的知识增加了，请您点个赞再离开,如果不嫌弃的话,点个关注再走吧，日更博主每天在线答疑 ! 当然，也非常欢迎您能在讨论区指出此文的不足处，作者会及时对文章加以修正 !如果有任何问题，欢迎评论，非常乐意为您解答！( •̀ ω •́ )✧