ABC 038 D プレゼント

qiita.com

DP問題で、泣いちゃった。

atcoder.jp

LIS(Longest Increasing Subseaquence)という問題らしい。

pekempey.hatenablog.com

この人のがめちゃめちゃわかりやすいかったです。

以下実装

""" 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()