Submission #4629821

---

Source Code Expand

# 最長増加部分列(Longest Increasing Subsequence)

# "抜き取り、挿入する"という操作をしないカードはもともと昇順になっている
# それらの操作をしないカードが最大になるように操作するカードを選ぶことが最小回数で済ませる条件
# つまり、もともと昇順になっているカード群を最大化すればよい
# これをDPで行う
N = int(input())
c = [int(input()) for i in range(N)]
dp = [1]  # dp[i]:i番目までのカードでの昇順カード群の大きさの最大
for i in range(1, N):
    #dp[i]=max([dp[j] for j in range(len(dp)) if c[j]<c[i] ])+1
    dp.append(max([0]+[dp[j] for j in range(len(dp)) if c[j] < c[i]])+1)
print(N-dp[N-1])

Submission Info

Judge Result