\(i\) 番目の人の時点での最小の労力を \(S(i)\) とすると,

\[\begin{align} S(i) &= \min_{1 \leq j \leq i} \{ S(j-1) + (a_i-x_j)^2 + y_j^2 \} \\ &= \min_{1 \leq j \leq i} \{ -2a_ix_j + S(j-1) + x_j^2 + y_j^2 \} + a_i^2 \end{align}\]

となる.

このままでは \(O(N^2)\) の計算量となるが, Convex Hull Trick を用いて \(O(N)\) に落とすことができる.