백준 7476번: 최대 공통 증가 수열 [C++]

작성일 | In
플래티넘 V 플래티넘 V

문제

최대 공통 증가 수열

풀이

$A[i] = B[j]$일 때 $dp[i][j]$를 두 부분 수열 $A_1, A_2, \dots, A_i$와 $B_1, B_2, \dots, B_j$의 최대 공통 증가 수열의 길이라 합시다.

$k < i$이고 $l < j$이면서 $A[k] = B[l]$을 만족하는 $k$, $l$에 대해 $dp[i][j] = \max(dp[k][l] + 1)$입니다.

이때 $l$은 $A[k] = B[l]$과 $l < j$를 만족하는 최댓값만 고려해도 됩니다.

만약 $l < m$이고 $B[l] < B[m]$인 $m$이 존재하여 이를 고려해야 한다면 $A[k] = B[m]$인 경우에서 고려되기 때문입니다.

따라서 $A[i] = B[j]$인 $j$를 오름차순으로 저장하여 가장 큰 $l$을 이분 탐색으로 구하면 시간 복잡도 $\mathcal{O}(M^3\log M)$에 해결할 수 있습니다.

코드

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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <bits/stdc++.h>
#ifndef ONLINE_JUDGE
#define ASSERT(x) assert(x)
#else
#define ASSERT(ignore) ((void)0)
#endif
using namespace std;

int A[555], B[555];
vector<int> sameIdx[555];

int lcis[555][555];
pair<int, int> prevPair[555][555];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int M1;
    cin >> M1;
    for (int i = 1; i <= M1; i++)
        cin >> A[i];

    int M2;
    cin >> M2;
    for (int i = 1; i <= M2; i++)
        cin >> B[i];

    for (int i = 1; i <= M1; i++) {
        for (int j = 1; j <= M2; j++) {
            if (A[i] == B[j]) {
                sameIdx[i].push_back(j);
                lcis[i][j] = 1;
            }
        }
    }

    for (int i = 1; i <= M1; i++) {
        for (int j = 1; j <= M2; j++) {
            if (A[i] != B[j])
                continue;

            for (int k = 1; k < i; k++) {
                if (A[k] >= A[i])
                    continue;

                auto it = lower_bound(sameIdx[k].begin(), sameIdx[k].end(), j);
                if (it == sameIdx[k].begin())
                    continue;

                int l = *(it - 1);
                ASSERT(A[k] == B[l] and A[i] > B[l]);
                if (lcis[k][l] + 1 > lcis[i][j]) {
                    lcis[i][j] = lcis[k][l] + 1;
                    prevPair[i][j] = pair(k, l);
                }
            }
        }
    }

    int ans = 0;
    int i = 0, j = 0;
    for (int k = 1; k <= M1; k++) {
        for (int l = 1; l <= M2; l++) {
            if (lcis[k][l] > ans) {
                ans = lcis[k][l];
                i = k, j = l;
            }
        }
    }

    cout << ans << '\n';

    stack<int> seq;

    while (i > 0 and j > 0) {
        seq.push(A[i]);
        auto [k, l] = prevPair[i][j];
        i = k, j = l;
    }

    ASSERT((int)seq.size() == ans);

    while (not seq.empty()) {
        cout << seq.top() << ' ';
        seq.pop();
    }

    return 0;
}

백준 7476번: 최대 공통 증가 수열 [C++]