[알고스팟][C++] JLIS: 합친 LIS

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

 

수열 두개가 주어질 때 각 수열에서 LIS를 골라 크기순으로 합친 것을 합친 증가 부분 수열이라 부르기로 합시다. 이 중 가장 긴 수열을 합친 LIS, JLIS(Joined LIS)라고 부릅시다.

문제는 두 수열의 JLIS의 길이를 구하는 것이 목표입니다.

 

\[ jlis(indexA, indexB) = \text{A[indexA]와 B[indexB]에서 시작하는 합친 증가 부분 수열의 최대 길이} \]

점화식을 위처럼 설정해줍니다.

이 증가 부분 수열의 다음 숫자는 A[indexA+1] 이후, 또는 B[indexB+1] 이후의 수열 중 max(A[indexA], B[indexB])보다 큰 수 중 하나가 됩니다.

const ll NEGINF = numeric_limits<ll>::min();
int n, m, A[100], B[100];
int cache[101][101];

int jlis(int indexA, int indexB) {
	auto& ret = cache[indexA + 1][indexB + 1];
	if (ret != -1) return ret;

	ret = 2;
	ll a = (indexA == -1 ? NEGINF : A[indexA]);
	ll b = (indexB == -1 ? NEGINF : B[indexB]);
	ll maxElement = max(a, b);

	// 다음 원소 찾기
	for (int nextA = indexA + 1; nextA < n; ++nextA)
		if (maxElement < A[nextA])
			ret = max(ret, jlis(nextA, indexB) + 1);

	for (int nextB = indexB + 1; nextB < m; ++nextB)
		if (maxElement < B[nextB])
			ret = max(ret, jlis(indexA, nextB) + 1);

	return ret;
}

A[-1], B[-1]을 계산 편의를 위해 임의로 넣었기 때문에 마지막에 계산 결과에서 A[-1], B[-1]의 개수인 2를 빼야 결과값이 됩니다.

사용할 때는 jlis(-1, -1)-2 처럼 쓰면 됩니다.