tooh’s diary

半角全角、常体敬体が入り乱れるカオス

3/29 AtCoder(1ずつ増加するLIS)

こんばんは。その日の獣には、をやっとプレイし始めました。とーです。

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)