d_tutuz https://blog.hatena.ne.jp/d_tutuz/ 数学/競プロメモ https://tutuz.hateblo.jp/ 問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0550 制約 考え方 DPで数え上げする。 dp[i][j][k] := 今 i 番目で A が j 個で、今 k であるときにかかる最小の時間 とする。 切る位置に対してそれぞれ、切る or 切らない の2通りを考えることができる。それぞれのコストを求めて、最終的に min(dp[n][n/2][0], dp[n][n/2][1]) が解になる。ただしメモリ制約上 64 MB までなので dp[10000][5000][2] の配列をもつことができない。DPの更新の際に直… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Ftutuz.hateblo.jp%2Fentry%2F2018%2F12%2F02%2F103310" title="第9回 日本情報オリンピック本選2：お菓子の分割 - 数学/競プロメモ" 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 2018-12-02 10:33:10 rich https://tutuz.hateblo.jp/entry/2018/12/02/103310 1.0 100%