タグ

AlgorithmとAOJに関するagwのブックマーク (1)

  • Persistence

    人には様々なこだわりがあります。例えば、に関することでも「は読むと汚れるのでカバーを外して読む様にし、カバーはクリアファイルなどにとっておく」や「は 1巻から並んでいないと気が済まない」など様々はこだわりがあります。 太郎君もその一人で、はきちんと 1巻から順に並んでいないと気が済まないようです。そんな太郎君はとある小説にはまっています。その小説は全部で n 巻あり、各巻での厚さが異なります。太郎君はこの小説が大変気に入ったので、その小説専用の棚を買おうと思っています。しかし、部屋に大きな棚を置くとかなり狭くなってしまうので、出来るだけ棚の幅が小さくなるように工夫しなければなりません。床から天井の高さを測ったところ、どうやら m 段の棚なら置けることが分かりました。そこで、小説 n 巻をどのように分ければ m 段の棚の幅を最小に出来るでしょうか?もちろん、各段に納める小

    agw
    agw 2011/04/04
    n冊の本をm段の本棚に整列したまま詰めた場合の本棚の最小の幅を求める。メモ化再帰を用いて解く。それほど難易度は高くない。良問題。
  • 1