跳转至

最长公共子序列

P1439 【模板】最长公共子序列 - 洛谷

#6564. 最长公共子序列 - LibreOJ

模版

\(dp[i][j]\) 表示以 \(a[i]\) 和 \(b[j]\) 结尾的最长长度

代码
C++
 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
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int __OneWan_2024 = [](){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();
const int N = 5005;
int a[N], b[N];
int dp[N][N];
int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1 ; i <= n ; i++) {
        cin >> a[i];
    }
    for (int i = 1 ; i <= m ; i++) {
        cin >> b[i];
    }
    for (int i = 1 ; i <= n ; i++) {
        for (int j = 1 ; j <= m ; j++) {
            if (a[i] == b[j]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    cout << dp[n][m] << "\n";
    return 0;
}

\(a\) 对 \(b\) 的位置做最长不下降子序列

代码
C++
 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
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int __OneWan_2024 = [](){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();
const int N = 100005;
int a[N], b[N];
int main() {
    int n;
    cin >> n;
    for (int i = 1 ; i <= n ; i++) {
        cin >> a[i];
    }
    map<int, int> pos;
    for (int i = 1 ; i <= n ; i++) {
        cin >> b[i];
        pos[b[i]] = i;
    }
    vector<int> f(1);
    for (int i = 1 ; i <= n ; i++) {
        int x = pos[a[i]];
        auto it = upper_bound(begin(f), end(f), x);
        if (it == end(f)) {
            f.emplace_back(x);
        } else {
            *it = x;
        }
    }
    cout << f.size() - 1;
    return 0;
}

bitset 优化

代码
C++
 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
#include <bits/stdc++.h>
using namespace std;
int __OneWan_2024 = [](){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();
const int N = 70010;
const int B = 63;
const int M = N / B + 1;
using u64 = unsigned long long;
u64 f[M], bs[N][M];
int a[N], b[N];
int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0 ; i < n ; i++) {
        cin >> a[i];
    }
    for (int i = 0 ; i < m ; i++) {
        cin >> b[i];
    }
    int k = (n + B - 1) / B;
    for (int i = 0 ; i < n ; i++) {
        bs[a[i]][i / B] |= 1ULL << i % B;
    }
    for (int i = 0 ; i < m ; i++) {
        u64 c = 1;
        for (int j = 0 ; j < k ; j++) {
            u64 x = f[j];
            u64 y = f[j] | bs[b[i]][j];
            x <<= 1;
            x += c + ((~y) & ((1ULL << B) - 1));
            f[j] = x & y;
            c = x >> B;
        }
    }
    int ans = 0;
    for (int i = 0 ; i < k ; i++) {
        ans += __builtin_popcountll(f[i]);
    }
    cout << ans << "\n";
    return 0;
}