ARC097E Sorted and Sorted
600埋め
！スマートな解説ではなく、遠回りなACまでの流れを書きます。
問題概要
1〜N (N<=2000)のいずれかが書かれた白黒のボールが1つずつ、適当に並んでいる．
これらのボールを並び替えて、それぞれの色のボールが昇順になるようにする。
隣り合うボールを入れ替える処理を行える。
最小何回で実現できるか。
最初の考察
「隣り合う要素を入れ替えて昇順にする最小コスト」
→BITでは？
- 小さい要素から順に左端まで運ぶ。
- この時のコストは、動かしたいボールより左にある未処理のボールの数。（BITを使うと処理/未処理の更新と未処理のボールのカウントが簡単に行える。）
- 白と黒の候補のうち、コストの低い方を動かす。
サンプル通ったので提出。
→WA
次の考察
コストの大きな要素を先に運んだ方が良かったりする？
例を考える。
233211（白は読めないので赤で表示）
黒の1より赤の123の方が優先されると、合計コストは11。
最初に黒の1を動かすと合計コスト8で処理できる。
考察は振り出しに戻る。
遷移の図を書いていると、
「最後に動かした白黒それぞれのボールが同じなら、未処理のボールの配置は同じ。（コストは異なる。）」
ということに気づく。
233211の場合は次のような遷移で表現できる。
これはN^2のDPですね...。
最後の考察
それぞれの状態において、ボールを端まで動かすコストが求まればDPが書ける。
ボールを動かすコストの計算はO(N)...?
ここでBITを思い出して、DPのループを回しながらBITも更新していけば、ボールを動かすコストも簡単に計算できることに気づく。
提出。
→AC。やったぜ。
