AOJ - KLIS

AOJ - KLIS

아마 종만북으로 처음 알고리즘을 접한다면 이 때쯤부터 통곡의 벽이 올 수 있다.

일단 책에있는 설명과 다르지 않게 풀었고,

뒤에서부터 LDS 를 구하면 그것이 특정 숫자에서 시작할 수 있는 LIS 의 최대 길이가 나오므로, $O(Nl\log N)$에 구해준다.

이후 $i$ 에서 시작할 수 있는 최대 길이의 LIS의 개수들을 $O(N^2)$ 에 돌려준다.

이후 $O(N^2\log N)$ 으로 trace를 하는데, 책에선 이걸 $O(N^2)$에 찾을 수 있다고 했는데,

아마 이전 과정에서 전처리를 해두라는 것을 의미하는 것 같다.

void solve() {  
   int n, k;  
   cin >> n >> k;  
  
   vi a(n);  
   fv(a);  
   n++;  
   a.insert(a.begin(), -1e15);  
  
   vi m, lis_len(n);  
   for (int i = n - 1; i >= 0; i--) {  
      int j = lbi(m, -a[i]);  
      if (j == sz(m)) m.pb(-a[i]);  
      else m[j] = -a[i];  
      lis_len[i] = j + 1;  
   }  
   int LIS = sz(m);  
  
   vi dp(n + 1, -1);  
   function<int(int)> fn = [&](int i) -> int {  
      if (lis_len[i] == 1) return 1;  
      int &ret = dp[i];  
      if (~ret) return ret;  
      ret = 0;  
      for (int j = i + 1; j < n; j++) {  
         if (a[i] < a[j] && lis_len[i] - 1 == lis_len[j]) {  
            ret = min(ret + fn(j), int(1e12));  
         }  
      }  
      return ret;  
   };  
  
   k--;  
  
   vi ans;  
   function<void(int)> trace = [&](int i) -> void {  
      ans.pb(a[i]);  
      if (lis_len[i] == 1) {  
         return;  
      }  
      vector<pi> nxt_list;  
      for (int j = i + 1; j < n; j++) {  
         if (a[i] < a[j] && lis_len[i] - 1 == lis_len[j]) {  
            nxt_list.pb({a[j], j});  
         }  
      }  
      sort(all(nxt_list));  
      for (int j = 0; j < sz(nxt_list); j++) {  
         int M = fn(nxt_list[j].se);  
         if (M > k) {  
            trace(nxt_list[j].se);  
            return;  
         } else {  
            k -= M;  
         }  
      }  
   };  
   trace(0);  
  
   cout << sz(ans) - 1 << endl;  
   for (int i: ans) if (i != -1e15) cout << i << ' ';  
   cout << endl;  
}