ABC 038 D プレゼント
DP問題で、泣いちゃった。
LIS(Longest Increasing Subseaquence)という問題らしい。
この人のがめちゃめちゃわかりやすいかったです。
以下実装
""" LSI (最長部分増加列問題) """ import bisect def main(): n = int(input()) a = [] for i in range(n): w, h = [int(j) for j in input().split()] a.append([w, h]) a.sort(key=lambda x: (x[0], -x[1])) INF = 10000000 # dp を INF 埋めしておく dp = [INF for i in range(n+1)] for i in range(n): dp[bisect.bisect_left(dp, a[i][1])] = a[i][1] print(bisect.bisect_left(dp, INF)) if __name__ == '__main__': main()