verify/dp/longest_increasing_subsequence.test.cpp

• View this file on GitHub
• Last update: 2025-01-24 21:00:23+09:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_D

Depends on

• Longest Increasing Subsequence (最長増加部分列) (dp/longest_increasing_subsequence.hpp)

Code

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_D"

#include <iostream>
#include <vector>

#include "dp/longest_increasing_subsequence.hpp"

int main() {
    int n;
    std::cin >> n;
    std::vector<int> a(n);
    for (int i = 0; i < n; i++) std::cin >> a[i];
    std::cout << longest_increasing_subsequence(a) << '\n';
    return 0;
}

#line 1 "verify/dp/longest_increasing_subsequence.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_D"

#include <iostream>
#include <vector>

#line 2 "dp/longest_increasing_subsequence.hpp"

#line 4 "dp/longest_increasing_subsequence.hpp"
#include <limits>
#include <algorithm>

template <class T> int longest_increasing_subsequence(const std::vector<T>& a, bool strict = true) {
    // strict = true  -> A[i] <  A[i + 1]
    // strict = false -> A[i] <= A[i + 1]
    const int n = (int)(a.size());
    const T INF = std::numeric_limits<T>::max();
    std::vector<T> dp(n, INF);
    // dp 配列中に A[i] があったときに, どの値を書き換えるかを考えると lower か upper を区別できる
    if (strict) {
        for (int i = 0; i < n; i++) {
            *std::lower_bound(dp.begin(), dp.end(), a[i]) = a[i];  // strict なのでその値
        }
    } else {
        for (int i = 0; i < n; i++) {
            *std::upper_bound(dp.begin(), dp.end(), a[i]) = a[i];  // strict ではないのでその次の値
        }
    }
    return lower_bound(dp.begin(), dp.end(), INF) - dp.begin();
}
#line 7 "verify/dp/longest_increasing_subsequence.test.cpp"

int main() {
    int n;
    std::cin >> n;
    std::vector<int> a(n);
    for (int i = 0; i < n; i++) std::cin >> a[i];
    std::cout << longest_increasing_subsequence(a) << '\n';
    return 0;
}

Back to top page