No.013 C

最初の何日かで食い溜めして残りは絶食して最終的な満腹度が $0$ を下回らなければいい. 最終的な満腹度の計算にあたっては食事の順序は問わず, 高価な食事の回数 $x$ と普通な食事の回数 $y$ と食事抜きの回数 $z$ だけを見ればいい.

これを数式化すると, $x + y + z = N$, $H + Bx + Dy - Ez \gt 0$ の条件のもとで $Ax + Cy$ を最小化する問題となる.

この条件の式から $z$ を消去すると

$$H + Bx + Dy - Ez = H - EN + (B+E)x + (D+E)y$$

となり,

$$y \gt \frac{EN - H - (B+E)x}{D+E}$$

となる. よって, $x$ を決めたときの $y$ の最小値が求まるので, $0 \leq x \leq N$ のそれぞれの $x$ について必要な最小の金額を求め, これの最小値を求めればいい.