parukii https://blog.hatena.ne.jp/parukii/ parukiのブログ https://par.hateblo.jp/ DP Binary Indexed Tree 隣接要素同士の交換しかできないのだから、もし白または黒のみであれば、最小の操作回数は転倒数に等しい。 この問題では、白と黒の２色の並び方ごとに操作回数が異なる。しかし、白と黒の並びが定まれば、操作回数は一意に定まる。なぜなら、各並び方について、白黒区別なく先頭から1~2Nと番号をつけ直せば、ただの順列のソートであるため。 先頭の要素からソートしていく。 dp[w][b]:=「先頭へ詰めて白1~w, 黒1~bをソート済みのときの最小の操作回数」 とおく。先頭からw+b個はソート済みということ。 このとき、次に白、黒のどちらがきても dp[w+1][b]またはdp[w][b+1]のどちらかを更新す… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fpar.hateblo.jp%2Fentry%2F2018%2F05%2F13%2F225827" title="E - Sorted and Sorted | AtCoder Regular Contest 097 - parukiのブログ" 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 2018-05-13 22:58:27 rich https://par.hateblo.jp/entry/2018/05/13/225827 1.0 100%