最长公共上升子序列(LCIS)

发表于 阅读次数：
板子

什么是最长公共上升子序列(bushi)

最长公共上升子序列就是最长的公共的上升的子序列(子序列不需要连续哦)

解决

想法

显然考虑dp, $ dp_{i,j} $ 表示选取序列 a 的前 i 个元素, lcis以 $ b_i $ 结尾的最长公共子序列的长度

状态转移方程

  1. $ a_i \neq b_i $ : $ dp_{i, j} \gets dp_{i - 1, j} $
    //如果 $ a_i \neq b_i $ , 那么在以 $ b_i $ 结尾的公共子序列中一定不选 $ a_i $
  2. $ a_i = b_i $ : $ dp_{i, j} \gets max(dp_{i - 1, k}), k < j $
    ////如果 $ b_k $小于 $ b_j $, 那么便可由 $ b_k $ 转移, 注意 $ a_i $ 已经和 $ b_i $ 配对所以不考虑

附上代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define maxn 100020
#define rep(i, a, b) for(int i = (a); i <= (b); i ++)
#define love return
#define you 0

int dp[5001][5001];
int a[maxn], b[maxn];

signed main()
{
    freopen("a.in", "r", stdin);
    freopen("a.out", "w", stdout);

    int n, m; cin >> n;
    rep(i, 1, n) cin >> a[i];
    cin >> m;
    rep(j, 1, m) cin >> b[j];

    // rep(i, 1, n) cout << a[i] << " ";
    // cout << endl;
    // rep(i, 1, m) cout << b[i] << endl;
    // cout << endl;

    rep(i, 1, n)
    {
        rep(j, 1, m)
        { 
            dp[i][j] = dp[i - 1][j]; //如果a_i != b_i, 那么在以b_i结尾的公共子序列中一定不选a_i
            if(a[i] == b[j])
            {
                int mx = 0;
                rep(k, 1, j - 1)
                {
                    if(b[k] < b[j])
                    {
                        mx = max(mx, dp[i - 1][k]); //如果b[k]小于b[i], 那么便可由b[k]转移, 注意a_i已经和b_i配对所以不考虑
                    }
                }
                mx += 1;
                dp[i][j] = mx;
            }    
           
        }
    }
    int ans = 0;
    rep(i, 1, m) ans = max(ans, dp[n][i]);
    cout << ans << endl;

    love you;
}

优化

但考虑到最坏情况下复杂度会退化到 $ O(n^3) $, 所以有没有什么方案可以再进一步降低复杂度呢?

我们可以发现 $ a_i = b_j, b_j > b_k $ 和 $ a_i > b_j $ 是等价的.

所以在第二层循环中只需要记一个 mxdp 来维护当前 $ dp_{i, j} 的最大值就好

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define maxn 100020
#define rep(i, a, b) for(int i = (a); i <= (b); i ++)
#define love return
#define you 0

int dp[5001][5001];
int a[maxn], b[maxn];

signed main()
{
    freopen("a.in", "r", stdin);
    freopen("a.out", "w", stdout);

    int n, m; cin >> n;
    rep(i, 1, n) cin >> a[i];
    cin >> m;
    rep(j, 1, m) cin >> b[j]; 

    rep(i, 1, n)
    {
        int mx = 0;
        rep(j, 1, m)
        { 
            dp[i][j] = dp[i - 1][j];
            if(a[i] > b[j]) mx = max(mx, dp[i][j]);
            if(a[i] == b[j]) dp[i][j] = mx + 1;
        }
    }
    int ans = 0;
    rep(i, 1, m) ans = max(ans, dp[n][i]);
    cout << ans << endl;

    love you;
}

显然还可以使用滚动数组优化空间, 但滚动数组我不想写

寄