This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub gyouzasushi/library
#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'; }