[알고스팟] 합친 LIS ID: JLIS

2020/06/25 - [알고리즘] - 최장 증가 부분수열: LIS (Longest Increasing Sub-sequence)

최장 증가 부분수열: LIS (Longest Increasing Sub-sequence)

이전 포스팅에서 LIS 알고리즘을 다뤘는데요, 이번에는 확장된 LIS인 두 배열에서 최장 증가 부분 수열을 뽑는 문제에 대해 다루려고 합니다. 

문제 링크

algospot.com :: JLIS

두 배열 arr과 brr에서 각각 길이 0 이상의 증가 부분 수열을 구하여 크기 순서대로 합친 것을 JLIS라고 합니다.

JLIS 예시

 

dp[i][j] 배열을 arr[i] 와 brr[j]를 시작으로 했을때 LIS의 최대 길이로 정의하면

가장 마지막 값 max(arr[i], brr[j]) 보다 큰 값인 경우만 탐색하면 됩니다.

초기 arr[0]과 brr[0]을 정수 범위보다 작은 수로 (-2e16) 초기화 한 후, 모든 경우에 대하여 탐색하기 때문에 최대값을 구할 수 있는것 입니다. (약간의 트릭을 사용한 것이죠.)

#include <iostream>
#include <algorithm>
#include <vector>
#include <memory.h>
#include <queue>
using namespace std;
typedef long long ll;
ll n,m,arr[101],brr[101] ,dp[101][101];

int t;
ll recv(ll a, ll b) { // a~ , b~ 에서 골랐을때 최대 길이
	if (~dp[a][b]) {
		return dp[a][b];
	}
	dp[a][b] = 0;
	ll _max = max(arr[a], brr[b]);
	for (int i = a; i <= n; i++) {
		if(_max < arr[i])
			dp[a][b] = max(dp[a][b], recv(i, b)+1);
	}
	for (int i = b; i <= m; i++) {
		if (_max < brr[i])
			dp[a][b] = max(dp[a][b], recv(a, i) + 1);
	}
	return dp[a][b];
}
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> t;
	for (; t--;) {
		cin >> n >> m;
		arr[0] = -2e16;
		brr[0] = -2e16;
		for (int i = 1; i <= n; i++) {
			cin >> arr[i];
		}
		for (int i = 1; i <= m; i++) {
			cin >> brr[i];
		}
		memset(dp, -1, sizeof(dp));
		cout << recv(0,0)<<endl;
	}
}