LISのテスト
(test/aoj/DPL_1_D.test.cpp)

• View this file on GitHub
• Last update: 2021-07-22 22:46:30+09:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_D

Depends on

• 最長増加部分列 (LIS) (util/lis.hpp)

Code

// @brief LISのテスト
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_D"
#include "../../util/lis.hpp"

#include <iostream>
using namespace std;

int main() {
  int n; cin >> n;
  vector<int> la(n);
  for (int i = 0; i < n; ++i) {
      cin >> la[i];
  }
  vector<int> len;
  cout << longest_increasing_subsequence(la, true, len) << endl;
}

#line 1 "test/aoj/DPL_1_D.test.cpp"
// @brief LISのテスト
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_D"
#line 1 "util/lis.hpp"
// @brief 最長増加部分列 (LIS)

#include <vector>
#include <algorithm>
template< typename T >
int longest_increasing_subsequence(const std::vector<T> &a, bool strict, std::vector<int> &len) {
    std::vector<T> lis;
    typename std::vector<T>::iterator it;
    for (int i = 0; i < a.size(); ++i) {
        T p = a[i];
        if(strict) it = std::lower_bound(lis.begin(), lis.end(), p);
        else it = std::upper_bound(lis.begin(), lis.end(), p);

        // a[0],...,a[i]までの最長増加部分列の長さ
        int pos = distance(lis.begin(), it);
        len.push_back(pos+1);

        if(lis.end() == it) lis.emplace_back(p);
        else *it = p;
    }
    return lis.size();
}
#line 4 "test/aoj/DPL_1_D.test.cpp"

#include <iostream>
using namespace std;

int main() {
  int n; cin >> n;
  vector<int> la(n);
  for (int i = 0; i < n; ++i) {
      cin >> la[i];
  }
  vector<int> len;
  cout << longest_increasing_subsequence(la, true, len) << endl;
}

Back to top page