Area1 https://blog.hatena.ne.jp/Area1/ Area1のif(memo[i][j]) https://area.hateblo.jp/ POJ 二分探索 貪欲 問題 要素数mの数列をk個の連続する数列に分割する。分割したそれぞれの数列の要素の和を計算し、そのうち最大となる値を最小化するように数列を分割したい。この条件をみたすように数列を分割して出力せよ。ただし複数の分割方法がある場合には、分割したはじめの数列の和のほうからなるべく小さくなるようにという方針で分割せよ。 やりかた 分割した数列中の和の最大値をXとすると、Xを大きくすると分割数kは小さくなる。なので二分探索で最適な和は計算することができる。 ただしこの問題は頭の方から小さく分割しろという条件が面倒。これには、数列を後ろの方から条件を満たしつつ、貪欲に大きく分割した後、余った分割数分、今度… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Farea.hateblo.jp%2Fentry%2F2017%2F03%2F07%2F223949" title="POJ 1505 Copying Books - Area1のif(memo[i][j])" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2017-03-07 22:39:49 rich https://area.hateblo.jp/entry/2017/03/07/223949 1.0 100%