yukicoder No.703 - ゴミ拾い Easy

問題

Convex-Hull Trickの入門に最適な問題。

DPの更新式を変形することでmin({ A[1]*x + B[1], ..., A[i]*x + B[i] })の形を得て、これはConvex-Hull Trickでの高速化を望める。