Submission #4631913

---

Source Code Expand

# 最長増加部分列(Longest Increasing Subsequence)
# "抜き取り、挿入する"という操作をしないカードはもともと昇順になっている
# それらの操作をしないカードが最大になるように操作するカードを選ぶことが最小回数で済ませる条件
# つまり、もともと昇順になっているカード群を最大化すればよい
# これをDPで行うのだが、データの持ち方を工夫して、カード群の大きさがiのときのカード群内の最大値が一番小さいものを格納
from bisect import bisect_left
N = int(input())
c = [int(input()) for i in range(N)]
dp = [c[0]]  # dp[i]:i枚カード群の中で、最大値が一番小さいカード群の、最後のカード
for i in range(1, N):
    for j in reversed(range(len(dp))):
        if dp[j] < c[i]:
            if j + 1 == len(dp):
                dp.append(c[i])
            else:
                dp[j + 1] = c[i]
            break
print(N-len(dp))

Submission Info

Judge Result