BOJ)13711 LCS4

문제: icpc.me/13711

LCS의 크기를 구하는 문제이다. 우리는 다이나믹 프로그래밍을 이용하여 LCS를 구할 수 있다.

하지만 LCS4 문제는 N이 10만이기 때문에 다른 방법을 생각해보아야 한다.

단순히 N이 10만에서 최장 공통 부분 수열을 구하라고 한다면 무척 어려운 문제가 되겠지만 다행히 조건이 더 주어진다.

1~N까지 정수는 두 수열 A,B에서 전부 한번 씩 주어진다는 것이다.

우리는 수열 A에서 입력을 받은 후 입력 받은 수의 인덱스로 A[x]의 들어온 순서를 삽입하는 방식으로 A수열을 정의 해준 뒤

A[B[i]]의 LIS를 구함으로서 최장 공통 부분 수열의 길이를 구할 수 있다.

이때 N이 10만이기 때문에 N^2 DP로 LIS를 구하는 방법은 안되고 NlogN 이분 탐색의 방법으로 LIS를 구해야 한다.

#include <cstdio>
#include <algorithm>
#include <vector>
#define MAX_N 100000
using namespace std;
int a[MAX_N + 1], b[MAX_N + 1], x, n, r;
vector<int> vt;
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &x);
        a[x] = i;
    }
    for (int i = 1; i <= n; i++) 
        scanf("%d", &b[i]);
    vt.push_back(-MAX_N - 100);
    for (int i = 1; i <= n; i++) {
        if (vt.back() < a[b[i]]) {
            vt.push_back(a[b[i]]);
            r++;
        }
        else {
            auto it = lower_bound(vt.begin(), vt.end(), a[b[i]]);
            *it = a[b[i]];
        }
    }
    printf("%d\n", r);
    return 0;
}