簡易版LARSCH (src/Optimization/simplified_larsch_dp.hpp)

View this file on GitHub
View document part on GitHub
Last update: 2023-10-29 17:46:55+09:00
Include: #include "src/Optimization/simplified_larsch_dp.hpp"

関数

名前	概要	計算量
`simplified_larsch_dp(N,w)`	\[\mathrm{dp}_ {i}=\begin{cases} 0 & i=0 \newline \min _{j\lt i}\lbrace\mathrm{dp}_j+w(i,j)\rbrace&i\gt 0\end{cases}\] の形のDPを解く. ただしコスト $w$ は Monge. 返り値は$\mathrm{dp}_i$ ( $i=0,\dots,N$ の $N+1$ 成分 )	$O(N\log N)$

参考

https://noshi91.hatenablog.com/entry/2023/02/18/005856

Verify

技術室奥プログラミングコンテスト#2 F - NPCの家 (NPC’s House) (Alien DP)

Depends on

関数型や関数オブジェクトに関するテンプレート (src/Internal/function_traits.hpp)

Verified with

Code

#pragma once
#include <vector>
#include <limits>
#include "src/Internal/function_traits.hpp"
// dp[i] = min_{j<i} (dp[j] + w(i,j))
// w(i,j) -> monge cost
template <class F> std::vector<result_type_t<F>> simplified_larsch_dp(int n, const F &w) {
 using T= result_type_t<F>;
 std::vector<T> dp(n + 1, std::numeric_limits<T>::max());
 std::vector<int> x(n + 1);
 auto check= [&](int i, int j) {
  if (T cost= dp[j] + w(i, j); dp[i] > cost) dp[i]= cost, x[i]= j;
 };
 auto rec= [&](auto &rec, int l, int r) {
  if (r - l <= 1) return;
  int m= (l + r) / 2;
  for (int i= x[l]; i <= x[r]; ++i) check(m, i);
  rec(rec, l, m);
  for (int i= l + 1; i <= m; ++i) check(r, i);
  rec(rec, m, r);
 };
 return dp[0]= 0, check(n, 0), rec(rec, 0, n), dp;
}

#line 2 "src/Optimization/simplified_larsch_dp.hpp"
#include <vector>
#include <limits>
#line 2 "src/Internal/function_traits.hpp"
#include <type_traits>
// clang-format off
namespace function_template_internal{
template<class C>struct is_function_object{
 template<class U,int dummy=(&U::operator(),0)> static std::true_type check(U *);
 static std::false_type check(...);
 static C *m;
 static constexpr bool value= decltype(check(m))::value;
};
template<class F,bool,bool>struct function_type_impl{using type= void;};
template<class F>struct function_type_impl<F,true,false>{using type= F *;};
template<class F>struct function_type_impl<F,false,true>{using type= decltype(&F::operator());};
template<class F> using function_type_t= typename function_type_impl<F,std::is_function_v<F>,is_function_object<F>::value>::type;
template<class... Args>struct result_type_impl{using type= void;};
template<class R,class... Args>struct result_type_impl<R(*)(Args...)>{using type= R;};
template<class C,class R,class... Args>struct result_type_impl<R(C::*)(Args...)>{using type= R;};
template<class C,class R,class... Args>struct result_type_impl<R(C::*)(Args...)const>{using type= R;};
template<class F> using result_type_t= typename result_type_impl<function_type_t<F>>::type;
template<class... Args>struct argument_type_impl{using type= void;};
template<class R,class... Args>struct argument_type_impl<R(*)(Args...)>{using type= std::tuple<Args...>;};
template<class C,class R,class... Args>struct argument_type_impl<R(C::*)(Args...)>{using type= std::tuple<Args...>;};
template<class C,class R,class... Args>struct argument_type_impl<R(C::*)(Args...)const>{using type= std::tuple<Args...>;};
template<class F> using argument_type_t= typename argument_type_impl<function_type_t<F>>::type;
}
using function_template_internal::result_type_t,function_template_internal::argument_type_t;
// clang-format on
#line 5 "src/Optimization/simplified_larsch_dp.hpp"
// dp[i] = min_{j<i} (dp[j] + w(i,j))
// w(i,j) -> monge cost
template <class F> std::vector<result_type_t<F>> simplified_larsch_dp(int n, const F &w) {
 using T= result_type_t<F>;
 std::vector<T> dp(n + 1, std::numeric_limits<T>::max());
 std::vector<int> x(n + 1);
 auto check= [&](int i, int j) {
  if (T cost= dp[j] + w(i, j); dp[i] > cost) dp[i]= cost, x[i]= j;
 };
 auto rec= [&](auto &rec, int l, int r) {
  if (r - l <= 1) return;
  int m= (l + r) / 2;
  for (int i= x[l]; i <= x[r]; ++i) check(m, i);
  rec(rec, l, m);
  for (int i= l + 1; i <= m; ++i) check(r, i);
  rec(rec, m, r);
 };
 return dp[0]= 0, check(n, 0), rec(rec, 0, n), dp;
}