테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.
====== LIS ======

===== 풀이 =====
  * 우선 A[0]으로 시작하는 부분배열들(=prefix들)의 LIS의 길이의 합을 구하는 것만 생각해보자
  * [[ps:tutorial:lis#a_i_로_끝나는_or_시작하는_lis_or_lds_의_길이|모든 i에 대해서 A[i]로 끝나는 LIS의 길이]]를 미리 구해둔다면, A[..i]의 LIS의 길이는 max({A[..i-1]의 LIS의 길이}, {A[i]로 끝나는 LIS의 길이}) 로 O(1)에 구할수 있고, 모든 prefix들의 LIS의 길이는 O(n)에 구할수 있다.
  * 모든 i에 대해 A[i]로 끝나는 LIS의 길이를 구하는 것은 O(nlogn)이므로, 총 시간복잡도는 O(nlogn)
  * 이제 이것을 다시 A[0:], A[1:], A[2:], ... 에 대해서 모두 구해주면 된다. 그러면 전체 시간복잡도는 O(n^2logn) 

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 9702. LIS".

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

Tags: [lis]
"""

import collections
import sys
from teflib import psutils
from teflib import seqtask


@psutils.gcj_style
def main():
    N = int(sys.stdin.readline())
    s = collections.deque(int(sys.stdin.readline()) for _ in range(N))

    answer = 0
    for _ in range(N):
        length = 0
        for l in seqtask.longest_inc_subseq_lengths_by_last_elem(s):
            if l > length:
                length = l
            answer += length
        s.popleft()

    print(answer)


if __name__ == '__main__':
    main()
</dkpr>
  * Dependency: [[:ps:teflib:seqtask#longest_inc_subseq_lengths_by_last_elem|teflib.seqtask.longest_inc_subseq_lengths_by_last_elem]]

{{tag>BOJ ps:problems:boj:골드_1}}