BOJ 2995 - 생일

BOJ 2995 - 생일

LIS 문제 특) 풀다가 LIS인걸 알아차림

역추적도 같이 해줘야한다.

놀랍게도(?) LIS는 일차원 배열이 아닌 pair 같은 것에 대해서도 적용할 수 있는 문제들이 종종 있다.

$(s,e)$ 를 $e$ 가 작은 순으로, $e$가 같다면 $s$ 가 큰 순으로 정렬한다고 하자.

그럼 $s$ 에 대한 LDS 문제가 된다.

$-s$에 대해 LIS를 해주자

이걸 구한 뒤 역추적 해주면 된다.

LIS 문제인데 중복된 수를 포함하는 LIS로 구현해줘야 함에 유의한다.

const int MAX = 1e6;  
void solve() {  
   int n;  
   cin >> n;  
   vector<pi> a(n);  
   for (auto &[l, r]: a) cin >> l >> r;  
   sort(all(a), [&](auto l, auto r) {  
      if (l.se != r.se) return l.se < r.se;  
      return l.fi > r.fi;  
   });  
   vi v, lis(n);  
   for (int i = 0; i < n; i++) {  
      auto &[l, r] = a[i];  
      int j = ubi(v, -l);  
      if (j == sz(v)) v.pb(-l);  
      else v[j] = -l;  
      lis[i] = j;  
   }  
   cout << sz(v) << endl;  
   int cur = sz(v) - 1;  
   for (int i = n; i-->0;)   
      if (cur == lis[i]) cout << a[i].fi << ' ' << a[i].se << '\n', cur--;  
}