[AOJ] DPL 1 D 最長増加部分列

2019年7月21日2020年9月27日

問題

方針

LIS: Longest Increasing Subsequence (最長部分増加列) という問題です。この問題では、狭義単調増加列の中で最も大きいものを求めます。

動的計画法と二分探索

参考を参照してください。

動的計画法とセグメント木

\( f_i \) を \( a_i \) の重複を許さない場合に何番目に大きいかという値とします。また、\( d(i) \) を \( i \) 番目に大きい値が末尾であるときの最長増加列の長さと定義します。

ここで、\( a_{0}\) から \( a_{i – 1} \) まで探索して \( d \) を構成し終えたとき、\( f_i \) について、

\[ d(f_i) < \max \left(d(0), d(1),\cdots, d(f_i – 1) \right) + 1\]

であるとき、

\[ d(f_i) \leftarrow \max \left(d(0), d(1),\cdots, d(f_i – 1) \right) + 1\]

と更新します。右辺の \( + 1 \) となっているのは、\( d(0)\) から \( d(f_i – 1) \) の末尾に \( a_i \) を追加し新しい最長増加列ができるためです。

コード

二分探索

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
vector<int> A, L;

int lis() {
  L[0] = A[0];
  int length = 1;
  for (int i = 1; i < n; i++) {
    if (L[length - 1] < A[i]) {
      L[length] = A[i];
      length++;
    } else {
      auto iter = lower_bound(L.begin(), L.begin() + length, A[i]);
      L[iter - L.begin()] = A[i];
    }
  }
  return length;
}

int main() {
  cin >> n;
  A.resize(n);
  L.resize(n);
  for (int i = 0; i < n; i++) {
    cin >> A[i];
  }
  cout << lis() << "\n";
  return 0;
}

セグメント木

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

struct SegmentTree {
private:
    int n;
    vector<int> node;
public:
    SegmentTree(int N) {
        n = 1;
        while(n < N) n *= 2;
        node.resize(2 * n - 1, 0);

    }

    void update(int k, int x) {
        k += (n - 1);
        node[k] = x;
        while (k > 0) {
            k = (k - 1) / 2;
            node[k] = max(node[2 * k + 1], node[2 * k + 2]);
        }
    }

    int query(int a, int b, int k = 0, int l = 0, int r = -1) {
        if (r < 0) r = n;
        if (r <= a || b <= l) return 0;
        if (a <= l && r <= b) return node[k];
        int vl = query(a, b, 2 * k + 1, l, (l + r) / 2);
        int vr = query(a, b, 2 * k + 2, (l + r) / 2, r);
        return max(vl, vr);
    }

};
int main() {
    int n;
    cin >> n;
    int a[n];
    set<int> s;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        s.insert(a[i]);
    }
    vector<int> v(s.begin(), s.end());
    SegmentTree st(n);
    int best = 0;
    for (int i = 0; i < n; i++) {
        int id = lower_bound(v.begin(), v.end(), a[i]) - v.begin();
        id++;
        int A = st.query(0, id);
        if (st.query(id, id + 1) < A + 1) {
            st.update(id, A + 1);
            best = max(best, A + 1);
        }
    }
    cout << best << "\n";
    return 0;
}

参考