[알고스팟] JLIS

JLIS

풀이

기존 LIS 문제와 같은 방식으로 풀 수 있다.

일단 A 수열에서 LIS, B 수열에서 LIS를 뽑으면 안 된다.

A에서 적게 뽑고 (LIS가 아닌 증가 부분 수열)
B에서 LIS를 뽑아도 그것은 답이 될 수 있다.

애초에 LIS의 길이가 몇인지 모르니
A에서 몇을, B에서 몇을 뽑을지도 모른다.
길이를 알더라도 그 길이에 해당하는 부분 수열은 여러개일 수 있다.
부분 수열의 종류에 따라 조합이 JLIS가 될지 안 될지는 아무도 모른다.

즉 이는 그리디한 방법으로는 풀 수가 없다.
미래를 예측할 수가 없기 때문이다.
A에서 $i$번째 수를 뽑거나 뽑지 않고,
B에서 $i$번째 수를 뽑거나 뽑지 않는 방식으로는 해결할 수 없다.
A에서 $i$보다 저 멀리에 있는 $j$번째 수를 뽑음으로서
결과가 달라질 수도 있다.
예를 들어 A = {1, 5, 9, 2}
B = {3, 4, 8, 10} 이라면
A에서 1과 2를 뽑고 나머지를 B로 채우는 게 옳은 선택일 것이다.

상황이 이런지라, A와 B를 동시에 차근차근 보는 것은 좋은 선택이 아니다.

일단 다이나믹 프로그래밍을 사용한다고 했을 때,
변수가 두 개가 되는 것은 쉽게 예상할 수 있다.

A에서 현재 보고 있는 인덱스와 B에서 현재 보고 있는 인덱스가 그것이다.

그리고 앞서 설명했듯 앞에서부터 보는 것은 해결책이 아니므로, for문으로 다 돌려봐야 한다.
그 for문은 A의 원소들을 다 선택해보는 것과 B의 원소들을 다 선택해보는 것이다.

원래 이중 for문을 쓰려고 했는데,
예외처리해야 할 것이 너무 많아졌다.
그래서 for문을 두 개로 나누는 것이 낫다고 생각을 했다.

점화식은
$dp(a, b) = max(max_{i < n}(dp(a_i,\ b)) + 1,\ max_{j < m}(dp(b_j,\ a)) + 1)$ 이다.

코드

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <climits>

#define MAX 100 + 1
using namespace std;
typedef long long ll;

int n, m;
ll A[MAX], B[MAX];
int dp[MAX][MAX];
void tc();
int JLIS(int, int);

int main() {
    int C;
    scanf(" %d", &C);
    for (int i = 0; i < C; i++) {
        tc();
    }
    return 0;
}

void tc() {
    scanf(" %d %d", &n, &m);
    for (int i = 1; i <= n; ++i) {
        scanf(" %lld", A + i);
    }
    for (int i = 1; i <= m; ++i) {
        scanf(" %lld", B + i);
    }
    memset(dp, -1, sizeof(dp));
    A[0] = B[0] = LLONG_MIN;
    printf("%d\n", JLIS(0, 0) - 2);
}

int JLIS(int aStart, int bStart) {
    int& ret = dp[aStart][bStart];
    if (ret == -1) {
        ret = 2;
        ll x = max(A[aStart], B[bStart]);
        for (int i = aStart + 1; i <= n; ++i) {
            if (x < A[i])
                ret = max(ret, JLIS(i, bStart) + 1);
        }
        for (int i = bStart + 1; i <= m; ++i) {
            if (x < B[i])
                ret = max(ret, JLIS(aStart, i) + 1);
        }
    }
    return ret;
}