こんばんは。その日の獣には、をやっとプレイし始めました。とーです。
AGC024C
解説がの最後らへんが意味不明だったので最初の方に準拠して考えます
問題の趣旨としては「数列中の数字を適切に数列の先頭か末尾に持って行って昇順に復元してくださいね」という感じ
実際、「入れ替えるべき数字」より「入れ替えるべきでない数字」を考えた方がよく、そのような数字群は「連続していてかつ昇順に並んでいる」という条件を満たしている
つまり、そのような数字群の中で最も含む要素数が多いような部分の長さを考え、全体から引くようにすればよい
例えば
1 8 9 2 3 5 7 4 6
という数列の中で、上記の条件を満たす最長の部分列は1 2 3 4である
これを求めるには、まず0埋めしたリストdpとBoolのリストTFを持っておいて（どちらも1インデックス）、数列を前から見ていったとき、
①今見た数字iをTrueにする
②そのひとつ前の数字i-1がTrueになっていたら（つまり数列内で既出で、TF[i-1] == True）、dp[i] = dp[i-1]+1とする
といったような更新を行っていけばよい
以下はpython3による答えのコード
N = int(input()) L = [] for i in range(N): L.append(int(input())) TF = [False]*(N+1) dp = [0]*(N+1) for i in range(N): TF[L[i]] = True if TF[L[i]-1] == True: dp[L[i]] = dp[L[i]-1]+1 print(N-max(dp)-1)
