AOJ - JLIS

AOJ - JLIS

사실 이 문제는 종만북에서 난이도가 하지만 꽤 어렵다.

일단 반복문 DP로 풀기는 구현이 잘 안나와서 재귀로 틀었다.

$dp_{i,\,j}$ = 현재 $a$의 인덱스가 $i$ 이고 $b$의 인덱스가 $j$ 일 때 끝까지 JLIS 를 구성했을 때 최대 길이라고 하자.

이제 $a_i$나 $b_j$ 보다 큰 값으로 나아갈 수밖에 없다. 왜냐면 $a_i$와 $b_j$ 는 이미 수열에 포함되었기 때문에 그 다음에 나오는 수는 이 두개보다 커야 하기 때문이다.

따라서 $i+1$ 보다 큰값이나 $j+1$ 보다 큰 값중에 $a_i$ 와 $b_j$ 보다 큰 값을 가진 수로 점프해줘서 dp를 구해주면 된다.

void solve() {  
   int n, m = 0;  
   cin >> n >> m;  
   vi a(n), b(m);  
   fv(a);  
   fv(b);  
  
   a.insert(a.begin(), -1e15);  
   b.insert(b.begin(), -1e15);  
  
   vvi dp(n + 1, vi(m + 1, -1));  
  
   function<int(int, int)> fn = [&](int l, int r) -> int {  
      int &ret = dp[l][r];  
      if (~ret) return ret;  
      ret = 0;  
  
      int mx = max(a[l], b[r]);  
  
      for (int i = l + 1; i <= n; i++) {  
         if (a[i] > mx) {  
            ret = max(ret, 1 + fn(i, r));  
         }  
      }  
      for (int i = r + 1; i <= m; i++) {  
         if (b[i] > mx) {  
            ret = max(ret, 1 + fn(l, i));  
         }  
      }  
  
      return ret;  
   };  
  
   cout << fn(0, 0) << endl;  
}