ABC#006 D.トランプ挿入ソート

その他

問題

1〜Nまで書かれたカードがシャッフルされた状態で積んである。
1回の操作で、各カードを1枚抜いて任意の場所に挿入することができる。
カードを上から昇順にするために必要な操作回数を答える。

N<=3*10^4

考え方

探索を考えると、各数字を上に持ってくるか下に持ってくるかという操作が考えられる。
が、任意の数字を任意のところに挿入できるので、その数字を除去する問題と考えられる。
「何個かの数字を除去して昇順になる数字を選ぶ最小回数」を考える。
これは「最長増加部分列(LIS)」と呼ばれる問題。


i番目の数字が部分列の最後尾だと考えた場合、最長で何個の数字が部分列に含まれるかを考えられれば、i+1番目でも同様に求められる。
これは、1〜i-1番目までで、i番目よりも小さい数字のところの「部分列に含まれる数字の個数」の中で一番大きいもの＋1がi番目の「部分文字列に含まれる数字の個数」の最大値になる。
dp[i]=max_{j=1〜i-1、ただしv[j]