사용자 도구

사이트 도구


ps:problems:boj:14002

가장 긴 증가하는 부분 수열 4

ps
링크acmicpc.net/…
출처BOJ
문제 번호14002
문제명가장 긴 증가하는 부분 수열 4
레벨골드 4
분류

LIS

시간복잡도O(nlogm)
인풋사이즈n<=1,000, m<=1,000
사용한 언어Python
제출기록34008KB / 156ms
최고기록56ms
해결날짜2021/06/15

풀이

코드

"""Solution code for "BOJ 14002. 가장 긴 증가하는 부분 수열 4".

- Problem link: https://www.acmicpc.net/problem/14002
- Solution link: http://www.teferi.net/ps/problems/boj/14002

Tags: [LIS] [SegmentTree]
"""

from teflib import segmenttree


def main():
    N = int(input())  # pylint: disable=unused-variable
    A = [int(x) for x in input().split()]

    size = max(A) + 1
    prev = []
    segtree = segmenttree.SegmentTree([(0, None)] * size, merge=max)
    for i, a in enumerate(A):
        max_len, pos = segtree.query(0, a)
        segtree.set(a, (max_len + 1, i))
        prev.append(pos)

    max_len, pos = segtree.query(0, size)
    answer = []
    while pos is not None:
        answer.append(A[pos])
        pos = prev[pos]

    print(max_len)
    print(*reversed(answer))


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
N R​ C J E
 
ps/problems/boj/14002.txt · 마지막으로 수정됨: 2021/12/23 12:05 저자 teferi