Jikka-5.0.11.1: A transpiler from Python to C++ for competitive programming

Jikka.Core.Convert.ConvexHullTrick

Description


Synopsis

# Documentation

run :: (MonadAlpha m, MonadError Error m) => Program -> m Program Source #

run optimizes a DP which has the recurrence relation $\mathrm{dp}(i) = \min a(j) x(i) + b(j) \lbrace \mid j \lt i \rbrace + c(i)$ where only appropriate elements of $$\mathrm{dp}$$ are used in $$a, x, b, c$$.

# internal rules

parseLinearFunctionBody parses the body of a linear function which can be decomposed to convex hull trick. parseLinearFunctionBody' f i j e finds a 4-tuple a, b, c, d where e = a(f[j], j) c(f[< i], i) + b(f[j], j) + d(f[< i], i).

TODO: What is the relation between j and k`?