LIS
- 最長増加部分列のこと
- 部分列において、狭義単調増加(a1 < a2 < a3 ... )
- 広義VERもある(下記)
解説
- https://ikatakos.com/pot/programming_algorithm/dynamic_programming/longest_common_subsequence
- 配列L[i] : 長さiのLISの中で末尾の最小値
- LISでありつつ末尾が小さいほどその後のLISを伸ばしやすいので、その情報だけ持てばいい
- 計算量 O(NlogN)
verify✅
- Longest Increasing Subsequence
- D - トランプ挿入ソート
感想
- 配列Lは単調増加
- なので後端だけ見る or 二分探索で高速に更新箇所を決められる
- ※配列LはLISではないことに注意
関連問題
- D - プレゼント
関数化
ll LIS(VI& A){ ll N = A.size(); VI L; L.push_back(A[0]); FOR(i, 1, N){ ll a = A[i]; if(L.back()<a){ L.push_back(a); }else{ auto it = lower_bound(ALL(L), a); *it = a; } } return L.size(); }
LIS復元
// sortedな列から検索。0-indexed // xの書き込み先を返す ll index_of(VI& A, ll x){ return distance(A.begin(), lower_bound(A.begin(), A.end(), x)); } // 復元可能 // http://www.prefield.com/algorithm/dp/lis_fast.html VI LIS(VI& a) { const int n = a.size(); VI A(n, inf); VI id(n); // Aのどこに挿入したかの情報 rep(i,n){ id[i] = index_of(A, a[i]); A[ id[i] ] = a[i]; } int m = *max_element(id.begin(), id.end()); VI b(m+1); // 後ろから for (int i = n-1; i >= 0; --i) if (id[i] == m){ b[m] = a[i]; m--; } return b; } int main(){ VI A = {5,3,7,4,1}; auto a = LIS(A); debug(a); return 0; }
出力
{3, 4}
- 参考先のを自分用に書き換えたもの。補助配列idを使うことで正しく復元できている
- TODO verify用問題
広義単調LIS
- a1 <= a2 <= a3 ... とイコールを許す
ll LIS2(VI& A){ ll N = A.size(); VI V; V.push_back(A[0]); FOR(i, 1, N){ ll a = A[i]; if(V.back()<=a){ //if(V.back()<a){ V.push_back(a); }else{ // auto it = lower_bound(ALL(V), a); auto it = upper_bound(ALL(V), a); *it = a; } } debug(V); return V.size(); }
- verified
- E - Sequence Decomposing
- https://atcoder.jp/contests/abc134/submissions/12062998
関連問題
- G - At Most Two