最长不下降子序列&最长公共子序列的O(n^2)以及O(n log n)解法

7.13 Chengdu

学了一天的 DP 问题，啥都没听懂，但是勉强听懂了最长不下降子序列的求法（我太弱啦），特发于此。

• • • • 二分查找的妙(误)用·最长不下降子序列
  • “二分查找的妙(误)用·最长不下降子序列” 的妙(误)用·最长公共子序列
  • “ ‘二分查找的妙(误)用·最长不下降子序列’ 的妙(误)用·最长公共子序列” 的妙(误)用

二分查找的妙(误)用·最长不下降子序列

最长不下降子序列作为DP的简单线性问题之一，其最常见的解法是 O(n^2) 的暴力枚举。用数组 a(i) 表示该序列中的第 i 项，用数组 f(i) 表示序列的前 项的最长不下降子序列长度，并初始化 f(1)=1 。假设当前已经求出 [1,i) 范围内的 f 数组的值，接下来求 ，只需要扫描 中每一个元素 j ，如果有 a(j) \leq a(i) ，那么 f(i)=max \{ f(i),f(j+1) \} 。

所以可以很容易得到其 代码：

    #include<bits/stdc++.h>
    using namespace std;
    int n,x,a[1100000],f[1100000],ans;
    int main()
    {
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
        f[i]=1;
        for(int j=0;j<n;j++)
            if(a[j]<=a[i]) f[i]=max(f[i],f[j]+1);
        ans=max(ans,f[i]);
    }
    printf("%d\n",ans);
    return 0;
    }

那么我们如何使用二分查找来优化算法达到 O(n\log n) 呢？

先定义一个数组 f(i) ，初始化全为 +\infty 。

这样的话怎么去更新数组呢？我们来拿一个序列做例子。这个序列的长度为 9 ，序列表示为：(3,5,1,2,4,7,6,8,9) 。

首先输入 ，按照升序插入数组 f 中。此时的 中的值均为 ，故 最小，插入到 f(1) 。

接下来插入 ， 比 要大，但显然比 要小，所以把它插入到 f(2) 。

接下来插入 ， 所有数字都要小，所以把它插入到 。

可是 替换掉了 啊，这没有关系吗？先不急，我们来插入下一个数字 。 比 大但是比 要小，所以我们把 插入到 。

接下来的步骤就简单了，我们依次插入序列当中剩余的部分。

插入完成后，我们回头来看原本的序列 ，用笔算一算，他的一个最长上升子序列是不是就是 数组中的 (1,2,4,6,8,9) ？

回到我们前面的疑问：为什么在插入时要直接删除掉数组当中已经储存的数字？假设我们不删除数组中的元素，而是取消插入，拿一个短一些的序列做例子： (3,1,2) 。插入 后。我们尝试插入 ，但是无法插入，只好插入下一项 ，也是无法插入。最终得到得 数组中的有效项（即非 项）为 (3) ，但 显然不是原序列中的最长上升子序列。

其实，在插入 时删除 运用到了一种贪心的思想：比 大的数要比比 大的数少（蜜汁绕口）。所以将 作为最长不上升子序列的备选项，就要比选取 更优。

当然，最终求出的 数组中有效项组成的序列并不一定是最长上升子序列，这里提供一组 hack 数据： (2,5,3) 但即使有这样的偏差存在，很容易发现，最终求出的 数组有效项的长度一定与原序列的最长上升子序列的长度相同。所以，这也可以作为最长不下降子序列的求解方式之一。

在这种求解方式中，最主要的操作是查询当前插入元素在 中的插入位置。我们始终保持 的单调不下降性质，那么就可以用二分查找的方式来优化朴素查找，来达到查找的 O(\log n) 时间复杂度。每个元素插入一次，总的时间复杂度就是 了。实现代码如下：

    #include<bits/stdc++.h>
    using namespace std;
    int n,x,f[1100000];
    int main()
    {
    scanf("%d",&n);
    memset(f,0x3f,sizeof f);
    for(int i=0;i<n;i++)
    {
        scanf("%d",&x);
        *upper_bound(f,f+n,x)=x;
    }
    printf("%d\n",lower_bound(f,f+n,0x3f3f3f3f)-f);
    return 0;
    }

注：

• upper_bound(f,f+n,x) 函数返回有序数列 f 中比 x 大的第一个数出现的最后一个位置（蜜汁饶舌*2），是 STL 库中的二分查找模板代码。需要注意的是，该函数返回的是一个地址。
• memset(f,0x3f,sizeof f) 函数的原理是按照变量储存的内存字节数来初始化数组的初值。比如说 int 储存占用了4个字节，那么用 memset() 来初始化 int 数组，就是把初值的二进制表示复制粘贴四遍并储存到 int 中，所以 upper_bound(f,f+n,x) 之后 f 数组中的每一个数的值为 0x3f3f3f3f 。特例是 bool 变量只占用了1个字节，而复制粘贴一遍就相当于初值本身，所以 bool 数组可以很愉快地使用该函数。

“二分查找的妙(误)用·最长不下降子序列” 的妙(误)用·最长公共子序列

最长公共子序列作为DP的简单线性问题之一，其最常见的解法是 O(n^2) 的暴力枚举。（我怎么好像在哪说过类似的话）。用数组 a(i) 表示该序列 A 中的第 项，用数组 b(i) 表示该序列 B 中的第 项，用数组 f(i,j) 表示序列 的前 项和序列 的前 j 项的最长公共子序列长度 。假设当前已经求出 f(i,j-1) ，接下来求 f(i,j) ，如果有 a(i)=b(j) ，那么 f(i,j)=f(i,j-1)+1 ，否则， f(i,j)=f(i,j-1) 。

实现代码如下：

    #include<bits/stdc++.h>
    using namespace std;
    const int SIZE=5100;
    int n,a[SIZE],b[SIZE];
    int f[SIZE][SIZE];
    int main()
    {
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++) scanf("%d",&b[i]);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            f[i][j]=max(f[i-1][j],f[i][j-1]);
            if(a[i]==b[j]) f[i][j]=max(f[i-1][j],f[i][j-1]+1);
        }
    printf("%d",f[n][n]);
    return 0;
    }

当然，因为这一次 是一个二维数组，所以空间上就不能那么的任性了，不过我们可以通过滚动数组这个黑科技来优化这一点。代码如下

    #include<bits/stdc++.h>
    using namespace std;
    const int SIZE=100005;
    int n,a[SIZE],b[SIZE];
    int f[SIZE];
    int main()
    {
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++) scanf("%d",&b[i]);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            f[j]=max(f[j],f[j-1]);
            if(a[i]==b[j]) f[j]=max(f[j],f[j-1]+1);
        }
    printf("%d",f[n]);
    return 0;
    }

可惜的是，这道题没有 的优化方式。

难道这篇博客就这样结束了吗?

不！虽然常规的最长公共子序列问题没有优化方式，但是我们可以研究非常规的啊。例如这一题：

Luogu P1439

细心的你在读完题之后一定发现了一个小细节：

输入格式：
第一行是一个数n，
接下来两行，每行为n个数，为自然数1-n的一个排列。

没错，这里的两个序列是两个排列。可是，这又有什么用呢？

我们把 a 数组中的数字用其数组下标置换，把 b 数组的数字用 数组的置换方法的相同方法来置换。说得并不是很清楚，但要是拿样例来做个例子的话：

既然 a(1)=3 ，那么我们就把 、 数组中出现的 都用 a(1) 的下标 代替：

既然 a(2)=2 ，那么我们就把 、 数组中出现的 都用 a(2) 的下标 代替：

既然 a(3)=1 ，那么我们就把 、 数组中出现的未被修改的 都用 a(3) 的下标 代替：

同理，对于 a(4)=4,a(5)=5 也用相同的方法替换：

这样，我们的替换就完成了。接下来，我们对 数组使用前文提到的最长不下降子序列就可以完成求解了。

等等！为什么可以这样？怎么突然问题就发生了转换？这是因为这时 的子序列一定是单调递增的，那么 、 $b$ 的最长公共子序列一定也是单调递增的。所以对于这个问题，就可以用最长不下降子序列来求解，代码如下：

    #include<bits/stdc++.h>
    using namespace std;
    const int MAXN=100005;
    int n,x,a[MAXN],b[MAXN],c[MAXN],f[MAXN];
    int main()
    {
    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]];
    }
    memset(f,0x3f,sizeof f);
    for(int i=1;i<=n;i++) *upper_bound(f,f+n,b[i])=b[i];
    printf("%d\n",lower_bound(f,f+n,0x3f3f3f3f)-f);
    return 0;
    }

“ ‘二分查找的妙(误)用·最长不下降子序列’ 的妙(误)用·最长公共子序列” 的妙(误)用

其实这个板块并不存在（逃

不过确实有这一类的题，是上一题的增强版，就是这两个序列并不只是排列，其中还有重复元素。那么这类题等我遇到了再来总结吧！