Convex-Hull Trickを蟻本の形のまま使える問題があったのでメモ。b[n-1] = 0に気付けると、 dp[0] = 0, dp[i] = min[j=0, i - 1] (dp[j] + b[j] * a[i]) (i >= 1) とすればO(N^2)で計算出来ることがわかる。 y = b[j] * x + dp[j]のa[i]での値であって、b[j]…