洛谷题单指南-动态规划2-P1439 【模板】最长公共子序列

原题链接：https://www.luogu.com.cn/problem/P1439

题意解读：求最长公共子序列的长度。

解题思路：

1、O(n^2)的方法：动态规划

设两个排列为a，b

设dp[i][j]表示a[1~i]与b[1~j]的最长公共子序列长度

根据公共子序列结尾是否包含a[i]、b[j]是否相等分情况讨论：

如果a[i] == b[j]

  则结尾包含a[i]和b[j]，所以dp[i][j] = dp[i-1][j-1] + 1，即a[1~i]与b[1~j]的最长公共子序列等同于a[1~i-1]与b[1~j-1]的最长公共子序列再加上1

如果a[i] != b[j]

  则结尾不包含a[i]或者不包含b[j]

• 不包含a[i]：所以dp[i][j] = dp[i-1][j]，即a[1~i]与b[1~j]的最长公共子序列等同于a[1~i-1]与b[1~j]的最长公共子序列
• 不包含b[j]：所以dp[i][j] = dp[i][j-1]，即a[1~i]与b[1~j]的最长公共子序列等同于a[1~i]与b[1~j-1]的最长公共子序列

对以上情况求max即可。

由于空间和时间复杂度都是O(n^2)，因此只能处理n=1000的情况。

50分代码：

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

const int N = 1005; //注意不能写100005，提交后数组内存超出限制，编译失败，但本地看不出来
int a[N], b[N];
int dp[N][N];
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++)
        {
            dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            if(a[i] == b[j]) dp[i][j] = max(dp[i][j], dp[i-1][j-1] + 1);
        }
    }
    cout << dp[n][n];

    return 0;
}

2、O(logn)的方法：LIS+二分

由于两个排列a、b都是1~n组成，只是顺序不同

举个例子：a = {3, 2, 1, 4, 5}，b = {1, 2, 3, 4, 5}

用一个桶数组h[]保存a中每个元素的位置：

h[3] = 1, h[2] = 2, h[1] = 3, h[4] = 4, h[5] = 5

再定义一个数组c用来表示b数组每个元素在a数组中的位置：

c = {3, 2, 1, 4, 5}

由于a中每个元素的下标是递增的，所以如果b中元素对应的a的位置是递增（也就是c中元素递增），那么可以认为和a是公共子序列

因此问题转换为：计算c中最长上升子序列的长度

要实现O(logn)的算法，可以采用此文介绍的单调栈+二分的方式进行优化。

100分代码：

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

const int N = 100005;
int a[N], b[N], h[N], c[N];
int s[N], top;
int n;

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i];
        h[a[i]] = i;
    } 
    for(int i = 1; i <= n; i++)
    {
        cin >> b[i];
        c[i] = h[b[i]];
    } 

    for(int i = 1; i <= n; i++)
    {
        if(top == 0 || s[top] < c[i]) s[++top] = c[i];
        else
        {
            int l = 1, r = top, ans = -1;
            while(l <= r)
            {
                int mid = (l + r) >> 1;
                if(s[mid] >= c[i])
                {
                    ans = mid;
                    r = mid - 1;
                }
                else l = mid + 1;
            }
            s[ans] = c[i];
        }
    }
    cout << top;

    return 0;
}