peroon https://blog.hatena.ne.jp/peroon/ perogram https://perogram.hateblo.jp/ Quiz https://yukicoder.me/problems/no/844 AC https://yukicoder.me/submissions/508731 dpテーブル VI dp(N+5, -A); // 最後に引いた線がiのときの最大スコア dp[0] = 0; 解説 右端ごとにまとめて、右端が小さいものから処理してDP マスに番号がありますが、私は線にも番号を付けました（下記画像）。こうするとdp[0]=0となっていい感じ 現在考えている範囲（(l, r, p)の組）を採用するとした時、過去のベストとぴったり端が一致するかどうかで線を引く本数が変わることに注意 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fperogram.hateblo.jp%2Fentry%2F2020%2F07%2F10%2F094030" title="No.844 split game - perogram" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn-ak.f.st-hatena.com/images/fotolife/p/peroon/20200710/20200710094024.png Hatena Blog https://hatena.blog 2020-07-10 09:40:30 rich https://perogram.hateblo.jp/entry/2020/07/10/094030 1.0 100%