Backfront [AtCoder Grand Contest 024 B]

https://agc024.contest.atcoder.jp/tasks/agc024_b

前提知識

• LIS（ちょっと違うけど）

解法

https://agc024.contest.atcoder.jp/submissions/2544563

挿入ソートみたいなことをやっている。
この問題が思い出されるのだが、操作で操作される要素ではなく残った要素に注目して考える。
残った要素に注目すると、操作で操作される要素は前後に自由に配置できるため、真ん中の列が残ることになる。
操作の回数を最小化したいということは、真ん中の列を最大化したいということである。
そのため、答えはN-(部分列の中で数が連続するもので最長の長さ)となる。
最長の長さを求めるにはLISのようにdpをつかってやれば良い。

int N, P[201010];
int dp[201010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> P[i];
 
    int ans = 0;
    rep(i, 0, N) {
        int p = P[i];
        dp[p] = dp[p - 1] + 1;
        chmax(ans, dp[p]);
    }
 
    cout << N - ans << endl;
}