글 읽기 - 바이토닉 수열 문제.

qkqhxla1 7년 전 1

분명히 다 잘 나오는것 같습니다. 반례좀 주시면 감사하겠습니다.

입

1
1

출

10
1 5 2 1 4 3 4 5 2 1

5
1 2 3 2 1

6
1 2 3 5 5 1

5
1 2 1 1 1

2
999 1000

ㅇ

from bisect import bisect_left
def lis(line):
    dp = [0 for i in xrange(1002)]
    fr = [0 for i in xrange(1002)]
    ck = [0 for i in xrange(1002)]
    size = 0
    for i in xrange(len(line)):
        h = bisect_left(dp[:size],line[i])
        if h==size: size += 1
        dp[h] = line[i]
        fr[dp[h]] = dp[h-1] if h else 0

    lis_list = []
    i=dp[size-1]
    while i:
        ck[i] = 1
        lis_list.insert(0,i)
        i = fr[i]
    return lis_list

n=input()
line = map(int,raw_input().split())
answer = 0
for i in xrange(n):
    l = lis(line[:i+1])
    d = lis(line[i:][::-1])[::-1]
    print l,d #확인용
    len_l = len(l)
    len_d = len(d)
    answer = max(answer, len_l+len_d-1)
print answer

bupjae 7년 전 1

"확인용" 은 지우고 제출하셔야...

qkqhxla1 7년 전 0

제출시 지우고 제출했습니다.... 혹시나 돌려보실 분들을 위하여...

seongkwonii 4년 전 1

1 2 3 3 2 1

...이걸 드디어 찾았네요

감사합니다 ㅠ

qkqhxla1 4년 전 0

@seongkwonii 하 -_-;;; 2년만에 찾았군요 감사합니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

바이토닉 수열 문제.

qkqhxla1 7년 전 1

bupjae 7년 전 1

qkqhxla1 7년 전 0

seongkwonii 4년 전 1

qkqhxla1 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말