합친 LIS

문제 : https://algospot.com/judge/problem/read/JLIS

문제

어떤 수열에서 0개 이상의 숫자를 지운 결과를 원 수열의 부분 수열이라고 부릅니다. 예를 들어 '4 7 6'은 '4 3 7 6 9'의 부분 수열입니다. 중복된 숫자가 없고 오름 차순으로 정렬되어 있는 부분 수열들을 가리켜 증가 부분 수열이라고 부르지요. 예를 들어 '3 6 9'는 앞의 수열의 증가 부분 수열입니다.

두 개의 정수 수열 A 와 B 에서 각각 증가 부분 수열을 얻은 뒤 이들을 크기 순서대로 합친 것을 합친 증가 부분 수열이라고 부르기로 합시다. 이 중 가장 긴 수열을 합친 LIS(JLIS, Joined Longest Increasing Subsequence)이라고 부릅시다. 예를 들어 '1 3 4 7 9' 은 '1 9 4' 와 '3 4 7' 의 JLIS입니다. '1 9' 와 '3 4 7' 을 합쳐 '1 3 4 7 9'를 얻을 수 있기 때문이지요.

A 와 B 가 주어질 때, JLIS의 길이를 계산하는 프로그램을 작성하세요.

코드 ( C ++ ) 종만북 참조

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring>

using namespace std;

int n, m;

const int MAX = 100 + 1;

int f[MAX];

int s[MAX];

int cache[MAX][MAX];

// 입력이 32비트 후보 있는 정수의 모든 값을 가질 수 있으므로

// 인위적인 최소치는 64비트여야 한다.

const long long NEGINF = numeric_limits<long long>::min();

// min(f[abegin] == s[bbegin]), max(f[abegin], s[bbegin])로 시작하는

// 합친 증가 부분 수열의 최대 길이를 반환한다.

// 단  abegin ==  bbegin == -1 혹은 f[abegin] != s[bbegin]라고 가정한다.

int solve(int abegin, int bbegin)

{

int& ret = cache[abegin + 1][bbegin + 1];

if (ret != -1)

return ret;

// f[abegin], s[bbegin]가 이미 존재하므로 2개는 항상 있다.

ret = 2;

long long a = (abegin == -1 ? NEGINF : f[abegin]);

long long b = (bbegin == -1 ? NEGINF : s[bbegin]);

long long maxE = max(a, b);

for (int nextA = abegin + 1; nextA < n; ++nextA)

if (maxE < f[nextA])

ret = max(ret, solve(nextA, bbegin) + 1);

for (int nextB = bbegin + 1; nextB < m; ++nextB)

if (maxE < s[nextB])

ret = max(ret, solve(abegin, nextB) + 1);

return ret;

}

int main()

{

int C;

cin >> C;

while (C--)

{

memset(cache, -1, sizeof(cache));

cin >> n >> m;

for (int i = 0; i < n; ++i)

cin >> f[i];

for (int i = 0; i < m; ++i)

cin >> s[i];

int ans = solve(-1, -1);

// abegin, bbegin -1 일때 2개 포함이므로 2빼준다.

cout << ans -2 << endl;

}

return 0;

}