Informatica Online Judge

  변형된 LIS [1287 / 0507]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 12   Total Tried : 117


The Champion of this Problem (C++) : jkjeong - 0ms / 799byte
My Best Submission (C++) : N/A

[koistudy.net (32nd 최재현)]

Background

LIS란 수열 S에서 몇 개의 수를 골라 이 수열이 증가 수열이 되는 가장 긴 부분 수열을 뜻한다.

경곽이는 여기서 변형시킨 LIS를 생각해 냈다.

변형된 LIS 수열은 LIS 수열 중에서 원래 수열에서 인접한 수열을 택할 수 없는 수열을 LIS를 뜻한다.

경곽이는 수열 S가 주어질 때 변형된 LIS 수열의 크기를 알아내고 싶어한다.

경곽이는 2000이하의 수열의 변형된 LIS를 찾는 것은 쉽다며, 더 긴 수열에서 변형된 LIS를 찾고 싶어 한다. 경곽이를 도와주자.

※주의 : 변형된 LIS는 단조 증가가 아니다. (등호를 포함하지 않는다.)

Input

첫 번째 줄에 수열의 길이 N이 주어진다.
그 다음 두 번째 줄에 공백과 함께 수열 S가 주어진다. (S의 i번째 원소를 Si라 하자)

[입력값의 정의역]
1 <= N <= 70,000
-100,000,000 <= Si <= 100,000,000

[Subtask Info]
#1 : (25점) N<=1,000
#2 : (75점) 추가 제약 조건이 없다.

Output

가장 큰 변형된 LIS 수열의 크기를 출력하라.

IO Example

입력 1

4
1 2 3 4

출력1

2

입력 2

8
2 8 6 7 2 8 2 1

출력2

3

예제 데이터 2 설명

원래 LIS 문제라면 2 6 7 8이 LIS지만, 7이 인접해 있기 때문에 선택 할 수 없어 2 6 8 이 변형된 LIS이다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]