hamayanhamayan https://blog.hatena.ne.jp/hamayanhamayan/ はまやんはまやんはまやん https://blog.hamayanhamayan.com/ 競技プログラミング https://atcoder.jp/contests/dp/tasks/dp_n 前提知識 区間DP 解説 https://atcoder.jp/contests/dp/submissions/3955596区間DPをする。 dp(L, R) := [L,R]の区間のスライムを1つにするためのコストの総和の最小値 自分は区間DPはメモ化再帰で実装するのが好きなので、そうしている。 ループで実装する場合は、区間が小さい方から順番に計算するように気をつけよう。 [L,R]の区間のスライムを1つにする一手前の状態を考えると、[L,R]が2つに別れていることが分かる。 なので、分ける境界を全探索して… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fblog.hamayanhamayan.com%2Fentry%2F2019%2F01%2F10%2F235656" title="Slimes [Educational DP Contest / DP まとめコンテスト N] - はまやんはまやんはまやん" 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 2019-01-10 23:56:56 rich https://blog.hamayanhamayan.com/entry/2019/01/10/235656 1.0 100%