JOI 春合宿 2007 day2-1 Building (難易度 5)

まさに LIS を求めよ、という問題！！

• ジャッジページ
• 問題文へのリンク

問題概要

個の整数からなる数列 が与えられる。これらの部分列であって、狭義単調増加であるもののうち、部分列の長さの最大値を求めよ。

制約

• 

考えたこと

LIS を求めよ、という問題。 が間に合う制約だが、実は で解けるのだ。

以下の記事に詳しく解説した。

qiita.com

コード

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

template<class T> int LIS(vector<T> a,  bool is_strong = true) {
    const T INF = 1<<30; // to be set appropriately
    int n = (int)a.size();
    vector<T> dp(n, INF);
    for (int i = 0; i < n; ++i) {
        if (is_strong) *lower_bound(dp.begin(), dp.end(), a[i]) = a[i];
        else *upper_bound(dp.begin(), dp.end(), a[i]) = a[i];
    }
    return lower_bound(dp.begin(), dp.end(), INF) - dp.begin();
}

int main() {
    int N;
    cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N; ++i) cin >> A[i];
    cout << LIS(A) << endl;
}