$\LARGE\color{orange}{刷题日记(算法提高课)}$

这道题在状态的定义上很大程度是借鉴了 AcWing 895. 最长上升子序列 和 AcWing 897. 最长公共子序列 ，这两题会的话这道题也能很快理解

LIS 中 $f[i]$ 的所表示集合为：所有以 $a[i]$ 为结尾的上升子序列

分析时考虑倒数第二个数的所有可能取值，并取整体的最大值（这里需要注意的是，最小值为 1）

LCS 中 $f[i][j]$ 所表示集合为：所有由 $a[0\sim i]$ 和 $b[0\sim j]$ 构成的公共子序列

分析时考虑 $a[i]$ 和 $b[j]$ 是否在公共子序列中，进而可以分出四种情况

这道题是 LCIS ，因此我们将二者结合一下，有：

$f[i][j]$ 表示集合为：所有由 $a[0\sim i]$ 和 $b[0\sim j]$ 构成并且以 $b[j]$ 为结尾的公共上升子序列（为了便于后面的讨论，我们以 $b[j]$ 为结尾，原因后面会说明）

属性为所有公共上升子序列当中的长度最大值

这里是思路过程与那两道题也类似，我们定义的是以 $b[j]$ 作为结尾，那么我们划分集合的依据就是 $a[i]$ 是否在公共上升子序列中

若 $a[i]$ 不在子序列，那么有 $f[i][j]=f[i-1][j]$ ，这里根据定义就可以判断

若 $a[i]$ 在子序列中，可以确定的是，由于该子序列是公共上升的，因此必然有 $a[i]==b[j]$ ，且该条件为充要条件

其次，由于我们是在 $a[i]$ 和 $b[j]$ 当中找公共上升子序列，因此对其单调性的判断，我们只需要看一边即可（$a[i]$ 或者 $b[j]$ 序列当中的子序列保证上升即可）

因此，我们只需要保证在 $b[j]$ 序列中的子序列是单调上升的即可（上升子序列的最小长度是 1 ）

完整代码：

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 3010;
int a[N], b[N];
int f[N][N];//表示集合: 由a[0~i], b[0~j]组成，以b[j]为结尾的公共上升子序列, 属性为长度最大值
int n;

int main()
{
    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++)
        {
            f[i][j] = f[i - 1][j];//a[i]不在公共上升子序列中
            if(a[i] == b[j])//a[i]在子序列中
            {
                f[i][j] = max(f[i][j], 1);//上升子序列的长度最小值为1
                for(int k = 1; k < j; k++)
                    if(b[k] < b[j])
                        f[i][j] = max(f[i][j], f[i - 1][k] + 1);//我们从同时去掉a[i]和b[j]的状态转移过来
            }                                                   //不能写成f[i][j] = max(f[i][j], f[i][k] + 1)
        }
    }

    int ans = 0;
    for(int i = 1; i <= n; i++) ans = max(ans, f[n][i]);
    cout << ans << endl;

    return 0;
}

这个代码是过不了的，有三重循环会导致超时

观察上述代码我们可以得出几个结论：

• 对 $f[i][j]$ 的赋值只会发生在 $a[i]==b[j]$ 时

• 第三重循环的目的是找到 $b[j]$ 序列中 $b[j]$ 前面满足 $b[k]<b[j]$ 的最大的值，相当于是求某个满足条件的前缀（$f[i-1][k]+1$）的最大值

• 第二重循环和第三重循环都会对 $j$ 便利一次，属于重复遍历

如果我们要求某个数的前缀的最大值的话，可以用一个变量 $maxv$ 来记录，如果当前值大于 $maxv$ ，那么就更新 $maxv$ ，之后遇到的每个数都可以做么做，具体实现如下：

$a[i]$ 为所给序列，$q[i]$ 为各个数所对应的前缀最大值

    int maxv = 0;
    for(int i = 1; i <= n; i++)
    {
        q[i] = max(maxv, a[i]);
        if(a[i] > maxv) maxv = a[i];
    }

类似的，由于第二层循环本身就会从小到大遍历一次 $j$ ，因此我们完全可以省略第三场循环，用一个变量 $maxv$ 来表示所有小于 $a[i]$ 的数的最大值，即所以 $a[i]$ 中满足条件的前缀的最大值

这里有一个问题是，为什么是 $a[i]$

这是因为只有在 $a[i]==b[j]$ 时才会对 $f[i][j]$ 进行赋值，即 $a[i]$ 和 $b[j]$ 是完全等价的，由于内层循环在不断改变 $j$ ，因此这里只能用 $a[i]$ 来判断

因此我们在 $a[i]==b[j]$ 时用 $maxv$ 对 $f[i][j]$ 进行更新，在满足 $a[i]>b[j]$ 时对 $maxv$ 进行更新

完整代码：

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 3010;
int a[N], b[N];
int f[N][N];//表示集合: 由a[0~i], b[0~j]组成，以b[j]为结尾的公共上升子序列, 属性为长度最大值
int n;

int main()
{
    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++)
    {
        int maxv = 1;//一定要放在外面
        for(int j = 1; j <= n; j++)
        {
            f[i][j] = f[i - 1][j];//a[i]不在公共上升子序列中
            if(a[i] == b[j])//只有在a[i]==b[j]时才会对f[i][j]赋值
                f[i][j] = max(f[i][j], maxv);
            if(b[j] < a[i])//在所有满足b[k]<b[j]的数中, 取最大值
                maxv = max(maxv, f[i - 1][j] + 1);
        }
    }

    int ans = 0;
    for(int i = 1; i <= n; i++) ans = max(ans, f[n][i]);
    cout << ans << endl;

    return 0;
}

更进一步，这里我们只会用到第 $i$ 层和第 $i-1$ 层，我们试着考虑空间优化

我们直接去掉第一维，有：

    for(int i = 1; i <= n; i++)
    {
        int maxv = 1;//一定要放在外面
        for(int j = 1; j <= n; j++)
        {
            if(a[i] == b[j])//只有在a[i]==b[j]时才会对f[i][j]赋值
                f[j] = max(f[j], maxv);
            if(b[j] < a[i])//在所有满足b[k]<b[j]的数中, 取最大值
                maxv = max(maxv, f[j] + 1);
        }
    }

空间优化时，我们需要考虑的问题是，当前更新的值是否会覆盖原先的值

在这里我们是先对 $f[j]$ 进行更新，并且 $f[j]$ 的更新只会用到他本身和 $maxv$ 因此这对 $f[j]$ 没有影响

接着我们需要考虑的是 $f[j]$ 更新后是否会对 $maxv$ 造成影响

$f[j]$ 的更新只会有两种情况，一是不变，另一个是变为 $maxv$

对于第一种情况，说明 $f[j]$ 的值比前缀最大值 $maxv$ 要大，$maxv$ 会自动更新到 $f[j]$ 的数值，这符合我们的预期

这里有一个问题是：$maxv$ 更新时用的是 $f[j]$ ，这不会导致 $maxv$ 的值不一样吗?

更新时是 $f[j]+1$，这里的加一指的是偏移量，即对于任意的 $f[j]$ ，用来更新 $maxv$ 的话都会比其本身大一

对于第二种情况，说明 $f[j]$ 的值小于 $maxv$ ，此时 $maxv$ 并不会更新（更新是取较大值）

因此我们直接去掉第一维便可以

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 3010;
int a[N], b[N];
int f[N];//表示集合: 由a[0~i], b[0~j]组成，以b[j]为结尾的公共上升子序列, 属性为长度最大值
int n;

int main()
{
    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++)
    {
        int maxv = 1;//一定要放在外面
        for(int j = 1; j <= n; j++)
        {
            if(a[i] == b[j])//只有在a[i]==b[j]时才会对f[i][j]赋值
                f[j] = max(f[j], maxv);
            if(b[j] < a[i])//只有在a[i]比当前记录的maxv大时，才会对maxv赋值
                maxv = max(maxv, f[j] + 1);
        }
    }

    int ans = 0;
    for(int i = 1; i <= n; i++) ans = max(ans, f[i]);
    cout << ans << endl;

    return 0;
}

关于开头的问题，为什么要定义以 $b[j]$ 作为结尾?

因为如果是 $a[i]$ 为结尾的话，那么 $i$ 需要作为第二层循环，这样下来后面两种做法的循环方式就会不同

当然非要这么定义也不会有问题，因为以 $a[i]$ 结尾和以 $b[j]$ 结尾，这两者是对偶的