動的計画法/最長増加部分列
(test/dynamic_programming/longest_increasing_subsequence.test.cpp)

• View this file on GitHub
• Last update: 2023-02-25 16:35:06+09:00
• Problem: https://judge.yosupo.jp/problem/longest_increasing_subsequence

Depends on

• 最長増加部分列 (longest increasing subsequence) (include/emthrm/dynamic_programming/longest_increasing_subsequence.hpp)

Code

/*
 * @title 動的計画法/最長増加部分列
 *
 * verification-helper: PROBLEM https://judge.yosupo.jp/problem/longest_increasing_subsequence
 */

#include <iostream>
#include <vector>

#include "emthrm/dynamic_programming/longest_increasing_subsequence.hpp"

int main() {
  int n;
  std::cin >> n;
  std::vector<int> a(n);
  for (int i = 0; i < n; ++i) {
    std::cin >> a[i];
  }
  std::vector<int> ans;
  int i = 0;
  for (const int lis_i : emthrm::longest_increasing_subsequence(a)) {
    while (a[i] != lis_i) ++i;
    ans.emplace_back(i++);
  }
  const int k = ans.size();
  std::cout << k << '\n';
  for (int i = 0; i < k; ++i) {
    std::cout << ans[i] << " \n"[i + 1 == k];
  }
  return 0;
}

#line 1 "test/dynamic_programming/longest_increasing_subsequence.test.cpp"
/*
 * @title 動的計画法/最長増加部分列
 *
 * verification-helper: PROBLEM https://judge.yosupo.jp/problem/longest_increasing_subsequence
 */

#include <iostream>
#include <vector>

#line 1 "include/emthrm/dynamic_programming/longest_increasing_subsequence.hpp"



#include <algorithm>
#include <iterator>
#include <limits>
#line 8 "include/emthrm/dynamic_programming/longest_increasing_subsequence.hpp"

namespace emthrm {

template <bool IS_STRICT = true, typename T>
std::vector<T> longest_increasing_subsequence(const std::vector<T>& a) {
  const T inf = std::numeric_limits<T>::max();
  const int n = a.size();
  std::vector<int> idx(n);
  std::vector<T> tmp(n, inf);
  for (int i = 0; i < n; ++i) {
    idx[i] = std::distance(
        tmp.begin(),
        IS_STRICT ? std::lower_bound(tmp.begin(), tmp.end(), a[i]) :
                    std::upper_bound(tmp.begin(), tmp.end(), a[i]));
    tmp[idx[i]] = a[i];
  }
  int res_size =
      std::distance(tmp.begin(), std::lower_bound(tmp.begin(), tmp.end(), inf));
  std::vector<T> res(res_size--);
  for (int i = n - 1; res_size >= 0 && i >= 0; --i) {
    if (idx[i] == res_size) res[res_size--] = a[i];
  }
  return res;
}

}  // namespace emthrm


#line 11 "test/dynamic_programming/longest_increasing_subsequence.test.cpp"

int main() {
  int n;
  std::cin >> n;
  std::vector<int> a(n);
  for (int i = 0; i < n; ++i) {
    std::cin >> a[i];
  }
  std::vector<int> ans;
  int i = 0;
  for (const int lis_i : emthrm::longest_increasing_subsequence(a)) {
    while (a[i] != lis_i) ++i;
    ans.emplace_back(i++);
  }
  const int k = ans.size();
  std::cout << k << '\n';
  for (int i = 0; i < k; ++i) {
    std::cout << ans[i] << " \n"[i + 1 == k];
  }
  return 0;
}

Back to top page