test/aoj/DPL_1_D.test.cpp

• View this file on GitHub
• Last update: 2022-09-02 13:25:33+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/courses/library/7/DPL/all/DPL_1_D

Depends on

• 最長増加部分列(LIS) (algorithm/longest_increasing_subsequence.hpp)

Code

#define PROBLEM \
    "https://onlinejudge.u-aizu.ac.jp/courses/library/7/DPL/all/DPL_1_D"
#include <bits/stdc++.h>

#include "../../algorithm/longest_increasing_subsequence.hpp"
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    int ans = longest_increasing_subsequence(a).size();
    cout << ans << '\n';
}

#line 1 "test/aoj/DPL_1_D.test.cpp"
#define PROBLEM \
    "https://onlinejudge.u-aizu.ac.jp/courses/library/7/DPL/all/DPL_1_D"
#include <bits/stdc++.h>

#line 3 "algorithm/longest_increasing_subsequence.hpp"
template <typename T, class Compare>
std::vector<T> longest_increasing_subsequence(const std::vector<T> &a,
                                              Compare comp) {
    const int n = a.size();
    std::vector<T> dp;
    std::vector<int> id(n);
    for (int i = 0; i < n; i++) {
        typename std::vector<T>::iterator it =
            std::lower_bound(dp.begin(), dp.end(), a[i], comp);
        id[i] = std::distance(dp.begin(), it);
        if (it == dp.end()) {
            dp.push_back(a[i]);
        } else {
            *it = a[i];
        }
    }
    std::vector<T> lis(dp.size());
    for (int i = n - 1, j = lis.size() - 1; i >= 0; i--) {
        if (id[i] == j) {
            lis[j--] = i;
        }
    }
    return lis;
}
template <typename T>
std::vector<T> longest_increasing_subsequence(const std::vector<T> &a) {
    return longest_increasing_subsequence(a, std::less<T>());
}
#line 6 "test/aoj/DPL_1_D.test.cpp"
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    int ans = longest_increasing_subsequence(a).size();
    cout << ans << '\n';
}

Back to top page