hamayanhamayan https://blog.hatena.ne.jp/hamayanhamayan/ はまやんはまやんはまやん https://blog.hamayanhamayan.com/ 競技プログラミング https://atcoder.jp/contests/yahoo-procon2019-qual/tasks/yahoo_procon2019_qual_d 前提知識 連結DP 解説 https://atcoder.jp/contests/yahoo-procon2019-qual/submissions/4212545今回の問題は一筆書きをしたときに通る回数と要求される回数との差を最小化する問題となる。 一筆書きという所と、最小化問題という所から、連結DPをしていく。 get(L,R) := A[L] + A[L+1] + ... + A[R]を累積和で用意しておこう。 dp[i][e] … 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fblog.hamayanhamayan.com%2Fentry%2F2019%2F02%2F10%2F013840" title="Ears [「みんなのプロコン 2019」 D] - はまやんはまやんはまやん" 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-02-10 01:38:40 rich https://blog.hamayanhamayan.com/entry/2019/02/10/013840 1.0 100%