VI dp(N+5, -A); // 最後に引いた線がiのときの最大スコア dp[0] = 0;
- 解説
- 右端ごとにまとめて、右端が小さいものから処理してDP
- マスに番号がありますが、私は線にも番号を付けました（下記画像）。こうするとdp[0]=0となっていい感じ
- 現在考えている範囲（(l, r, p)の組）を採用するとした時、過去のベストとぴったり端が一致するかどうかで線を引く本数が変わることに注意
VI dp(N+5, -A); // 最後に引いた線がiのときの最大スコア dp[0] = 0;