問題はこちら
問題概要
がいて,左から番目は人である.以下の種類の操作を繰り返し,人を昇順に並び替えるときのコストの最小値を求めよ.- コストを払い,人を好きな位置に移動させる.
- コストを払い,人を左端に移動させる.
- コストを払い,人を右端に移動させる.
解説
とする.それぞれの操作は元の位置によらないので,各人に対しての操作は高々回でいい.
操作をしない人を決める(ただし番号は昇順)ことにより,他の人に対する操作が決まる.例として以下の問題を考える.
人,人,人を操作しないと決める(選ばれなかった人は必ず動かす)
人は左端に移動する操作,人は好きな位置に移動する操作,人は右端に移動する操作を行う.より一般的には,操作をしないと決めたすべての人よりも数が小さい人は左端に移動し,操作をしないと決めたすべての人よりも数が大きい人は右端に移動し,その他の人は好きな位置に移動する操作を行う必要がある.
番号の昇順に操作をしない人を選ぶように考えることで以下のようなDPで解ける.
「番目まで決めて最後に人を選んだときの最小コスト」とする.元の順番で人より左側にいるような人について,人を選び,となる人は選ばないとするとの最小値がとなる.ただし,人を最初に選ぶときはとなる.
まとめると,.ただし,はかつ元の順番で人が人より左にいるようなの集合とする.
が高速に求められれば解ける.
の昇順にみたいなものを求めるのは典型で,の昇順にSegmentTreeのの位置にを入れていけば区間最小値を求める問題になって高速に解ける.
が求まれば,人の後の人は選ばないと考えることでの最小値が答えとなる.