Codeforces Round #650 F2-Flying Sort (Hard Version)

これを解説ACしました。

問題概要

長さ $n$ の配列 $a$ が与えられる。
配列内の要素を先頭に持っていく/最後尾に持っていくという操作を繰り返してソートしたい。
最低何回ソートをする必要があるか？

言い換え

ソート後の配列の連続部分列かつ $a$ の部分列である配列の長さの最大値を $n$ から引いたものを求める。

やること

座圧してDPをします。以降は座圧しているものとして考察を進めます。
$dp[x][j]:=部分列の最後の要素である\ x\ の状態が\ j\ であるときの長さの最大値、または\ x\ の数$
と定義します。 $dp[x][1]$ にのみ $x$ の数をもちます。
また、 $cnt[x]:=\ a\ 内の\ x\ の数$ とします。
$x$ の状態 $j$ について、全てを考慮すると $cnt[x]$ の数に一致します。
その時の計算量は $O(N^2)$ になってしまうので間に合いません。