test/LIS.test.cpp

• View this file on GitHub
• Last update: 2021-03-21 09:59:09+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/courses/library/7/DPL/1/DPL_1_D

Depends on

• DP/LIS.cpp

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/7/DPL/1/DPL_1_D"
#include "./../DP/LIS.cpp"
#include <iostream>
using namespace std;

int main() {
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	int n;
	cin >> n;
	vector<int> a(n);
	for (int& i : a) {
		cin >> i;
	}
	cout << LIS(a) << '\n';
}

#line 1 "test/LIS.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/7/DPL/1/DPL_1_D"
#line 2 "DP/LIS.cpp"
#include <vector>
#include <algorithm>
#include <limits>

template <class T> int LIS(const std::vector<T>& a) {
	constexpr T INF = std::numeric_limits<T>::max();
	std::vector<T> dp(a.size(), INF);
	for (auto num : a) {
		*std::lower_bound(dp.begin(), dp.end(), num) = num;
	}
	return std::lower_bound(dp.begin(), dp.end(), INF) - dp.begin();
}
#line 3 "test/LIS.test.cpp"
#include <iostream>
using namespace std;

int main() {
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	int n;
	cin >> n;
	vector<int> a(n);
	for (int& i : a) {
		cin >> i;
	}
	cout << LIS(a) << '\n';
}

Back to top page