test/aoj/DPL_1_D/main.test.cpp

• View this file on GitHub
• Last update: 2021-04-23 23:44:44+09:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_D
• Link: View error logs on GitHub Actions

Depends on

• Input vector (Mylib/IO/input_vector.cpp)
• Longest increasing subsequence (Mylib/Typical/longest_increasing_subsequence.cpp)

Code

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

#include <iostream>
#include <vector>
#include "Mylib/IO/input_vector.cpp"
#include "Mylib/Typical/longest_increasing_subsequence.cpp"

namespace hl = haar_lib;

int main() {
  int N;
  std::cin >> N;

  auto a = hl::input_vector<int>(N);

  auto ans = hl::longest_increasing_subsequence(a).size();
  std::cout << ans << std::endl;

  return 0;
}

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

#include <iostream>
#include <vector>
#line 4 "Mylib/IO/input_vector.cpp"

namespace haar_lib {
  template <typename T>
  std::vector<T> input_vector(int N) {
    std::vector<T> ret(N);
    for (int i = 0; i < N; ++i) std::cin >> ret[i];
    return ret;
  }

  template <typename T>
  std::vector<std::vector<T>> input_vector(int N, int M) {
    std::vector<std::vector<T>> ret(N);
    for (int i = 0; i < N; ++i) ret[i] = input_vector<T>(M);
    return ret;
  }
}  // namespace haar_lib
#line 2 "Mylib/Typical/longest_increasing_subsequence.cpp"
#include <algorithm>
#line 4 "Mylib/Typical/longest_increasing_subsequence.cpp"

namespace haar_lib {
  template <typename Container>
  std::vector<int> longest_increasing_subsequence(const Container &a) {
    using T = typename Container::value_type;

    const int N = a.size();

    std::vector<T> dp;
    dp.reserve(N);
    std::vector<int> prev(N, -1), pos, ret;
    pos.reserve(N);

    for (int i = 0; i < N; ++i) {
      auto x = a[i];
      if (dp.empty() or dp.back() < x) {
        dp.push_back(x);
        if (pos.size()) prev[i] = pos.back();
        pos.push_back(i);
      } else {
        const int k = std::lower_bound(dp.begin(), dp.end(), x) - dp.begin();
        dp[k]       = x;
        if (k > 0) prev[i] = pos[k - 1];
        pos[k] = i;
      }
    }

    int i = pos.back();
    while (i != -1) {
      ret.push_back(i);
      i = prev[i];
    }

    std::reverse(ret.begin(), ret.end());

    return ret;
  }
}  // namespace haar_lib
#line 7 "test/aoj/DPL_1_D/main.test.cpp"

namespace hl = haar_lib;

int main() {
  int N;
  std::cin >> N;

  auto a = hl::input_vector<int>(N);

  auto ans = hl::longest_increasing_subsequence(a).size();
  std::cout << ans << std::endl;

  return 0;
}

Back to top page