abc 134 E - Sequence Decomposing (python)
数列を前から見ていって、二分探索でその数字が今の数字の色の種類のどれに上書きできるかをを探して、上書きできる奴で、一番数が大きいものにその数字を上書きする。
貪欲法の練習問題で箱を入れていくやつと同じ考え方。
D - プレゼント
0 なら色の種類を +1 してその数字を一番前に appendleft かなんかで入れる。
import sys input = sys.stdin.readline n = int(input()) if n == 1: print(1) exit() chk = [] for i in range(n): a = int(input()) chk.append(a) from bisect import bisect_left,insort_left from collections import deque ans = 0 c = deque([]) for j in chk: if i == 0: c.append(j) else: ind = bisect_left(c,j) if ind == 0: ans += 1 c.appendleft(j) else: c[ind-1] = (j) print(ans) print(ans)