ThreeStones https://blog.hatena.ne.jp/ThreeStones/ ThreeStonesのアレ https://threestones.hateblo.jp/ 読書 問題概要 とても長い板からN個の板を切り出す。 切り出す板はL1,L2,...Lnであり、元の板の合計となっている。 板を切断する際に、その板の長さだけコストがかかる。 例えば２１の板を１３と８に分けた場合、コストは13+8である。 最小コストで板を切り出した場合のコストを出力せよ。入力 N：切り出す板の数 L：切り出す板の長さの配列 出力 cost：コスト 問題解法 常に切り出す場合、二つの板が出現し、コストはその合計となる。 切り出す板を短い順に並べて(一番切り出すのに回数が必要)、先頭二つをまず切り出す。 次に、切り出した二つを合計したものを、２つの板の代わりに配列へ入れて、再度ソート。… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fthreestones.hateblo.jp%2Fentry%2F2014%2F06%2F29%2F104100" title="FenceRepair - ThreeStonesのアレ" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> http://ecx.images-amazon.com/images/I/41bHxtpurqL.jpg Hatena Blog https://hatena.blog 2014-06-29 10:41:00 rich https://threestones.hateblo.jp/entry/2014/06/29/104100 1.0 100%