JOI2008 春合宿 - ナイルドットコム

• 問題
• AC

$f(x) := x$日目を終えた時点での最小金額 とするとき、

$$f(x) = \min \begin{cases} f(x-1) + 1日間同じ店で購入する場合の最小金額 \\ f(x-2) + 2日間同じ店で購入する場合の最小金額 \\ ... \\ f(0) + x日間同じ店で購入する場合の最小金額 \end{cases}$$

となっている。上から順に、つまり$k=1, 2, ..., x$という順に$k$日間同じ店で購入する場合の最小金額を求めていくのは、ひとつ前の情報を利用すれば${O}(N)$で可能なので、全体の計算量は${O}(ND^2)$になる。

この方針だと割り算を排除しないと通らなかった。実際のループ回数は$2 \times 10^8$くらい？

---

もっとましな方法があるらしいのであとで確認する。というか、2008年当時なら通ってなさそう。