動的計画法/スライド最小値
(test/dynamic_programming/slide_min.test.cpp)

• View this file on GitHub
• Last update: 2023-02-25 01:48:23+09:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_3_D

Depends on

• スライド最小値 (include/emthrm/dynamic_programming/slide_min.hpp)

Code

/*
 * @title 動的計画法/スライド最小値
 *
 * verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_3_D
 */

#include <iostream>
#include <vector>

#include "emthrm/dynamic_programming/slide_min.hpp"

int main() {
  int n, l;
  std::cin >> n >> l;
  std::vector<int> a(n);
  for (int i = 0; i < n; ++i) {
    std::cin >> a[i];
  }
  const std::vector<int> ans = emthrm::slide_min(a, l);
  for (int i = 0; i + l <= n; ++i) {
    std::cout << ans[i] << " \n"[i + l == n];
  }
  return 0;
}

#line 1 "test/dynamic_programming/slide_min.test.cpp"
/*
 * @title 動的計画法/スライド最小値
 *
 * verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_3_D
 */

#include <iostream>
#include <vector>

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



#include <deque>
#line 6 "include/emthrm/dynamic_programming/slide_min.hpp"

namespace emthrm {

template <bool IS_MINIMIZED = true, typename T>
std::vector<T> slide_min(const std::vector<T>& a, const int len) {
  const int n = a.size();
  std::vector<T> res(n - len + 1);
  std::deque<T> deq;
  for (int i = 0; i < n; ++i) {
    while (!deq.empty() &&
           !(IS_MINIMIZED ? a[deq.back()] < a[i] : a[deq.back()] > a[i])) {
      deq.pop_back();
    }
    deq.emplace_back(i);
    if (i + 1 >= len) {
      const int left = i + 1 - len;
      res[left] = a[deq.front()];
      if (deq.front() == left) deq.pop_front();
    }
  }
  return res;
}

}  // namespace emthrm


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

int main() {
  int n, l;
  std::cin >> n >> l;
  std::vector<int> a(n);
  for (int i = 0; i < n; ++i) {
    std::cin >> a[i];
  }
  const std::vector<int> ans = emthrm::slide_min(a, l);
  for (int i = 0; i + l <= n; ++i) {
    std::cout << ans[i] << " \n"[i + l == n];
  }
  return 0;
}

Back to top page