drken1215 https://blog.hatena.ne.jp/drken1215/ けんちょんの競プロ精進記録 https://drken1215.hatenablog.com/ AOJ AOJ-ICPC400点 ICPC国内予選 DP 数列 区間 区間DP 入れ子構造 操作 操作を好きな回数だけ行える 操作後の結果の最適化問題 最大回数・最大個数を求める AOJ-ICPC 最適化問題 操作:削除 制約条件:隣接する要素について 操作:隣接する2個を削除 このブログの「区間 DP」タグを充実させたい。この問題は本当に典型的な区間 DP なのでちょうどいい！！！ 問題へのリンク 問題概要 長さ の整数数列 が与えられる。これらに対して以下の操作を好きな順序で好きな回数だけ行う。 値の差が 1 以下であるような、隣接する 2 つの要素を選び、2 つまとめて削除する 操作によって削除される要素の個数の最大値を求めよ。 制約 考えたこと この手の「列の中の隣接する 2 項について処理を順次行う」というタイプの問題に対しては スタックを用いたシミュレーション 区間 DP といった手法が有効であることが多い。前者の例として「カッコ列の整合性判定」、後者の例… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fdrken1215.hatenablog.com%2Fentry%2F2020%2F03%2F10%2F160500" title="AOJ 1611 ダルマ落とし (ICPC 国内予選 2016 D) (400 点) - けんちょんの競プロ精進記録" 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.user.blog.st-hatena.com/default_entry_og_image/80936665/1687765056723440 Hatena Blog https://hatena.blog 2020-03-10 16:05:00 rich https://drken1215.hatenablog.com/entry/2020/03/10/160500 1.0 100%