20091번 - Mountains 서브태스크다국어언어 제한함수 구현

문제

Tahmuras, the third king of ancient Persia, has conquered a huge army of deevs (demons). He wants to imprison as many of them as possible in Alborz mountains and let the others go. Alborz is a mountain range with a skyline that looks like a polygonal chain with $n$ vertices. The $i$-th vertex (for all 0ドル \le i \le n - 1$) has coordinates $(i, y[i]),ドル i.e. with longitude $i$ and altitude $y[i]$.

The deevs can be imprisoned on different vertices. No two imprisoned deevs should be able to see each other; otherwise, they will make eye contact and plan to escape. Two deevs cannot see each other if there is at least one vertex between them that is strictly higher than a line connecting their vertices.

In the following figure, a deev on vertex 0ドル$ can see deevs on vertices 1ドル$ and 2ドル$. But it cannot see deevs on vertices 3ドル,ドル 4ドル$ and 5ドル,ドル since vertex 2ドル$ is higher than the line connecting vertex 0ドル$ to any of vertices 3ドル,ドル 4ドル,ドル or 5ドル$.

Your task is to help Tahmuras find the maximum number of deevs that can be imprisoned in Alborz mountains.

구현

You should implement the following procedure. It will be called by the grader once for each test case.

int maximum_deevs(int[] y)

• $y$: integer array of length $n,ドル the altitude of the vertices
• This procedure should return the maximum number of deevs that can be imprisoned.

입력

출력

제한

• 1ドル \leq n \leq 2000,ドル
• 0ドル \leq y[i] \leq 10^9$ (for all 0ドル \leq i < n$).

예제 1

Consider the polygonal chain given in the above figure.

maximum_deevs([6, 1, 5, 2, 3, 1])

The answer is 3ドル$. One possible solution is to imprison deevs on vertices 1ドル,ドル 3ドル$ and 5ドル$.

예제 2

maximum_deevs([0, 1, 2])

The answer is 1ドル$. The deevs imprisoned on any pair of vertices can see each other (vertex 1ドル$ is on the line connecting vertices 0ドル$ and 2ドル,ドル not strictly higher).

서브태스크

힌트

샘플 그레이더

The sample grader reads the input in the following format:

• line 1ドル$: $\;\;n$
• line 2ドル$: $\;\;y[0] \;\; y[1] \;\; y[2] \;\ldots\; y[n-1]$

The sample grader prints a single line containing the return value of maximum_deevs.

첨부

• grader.cpp
• mountains.cpp
• mountains.h
• 01.in
• 01.out
• 02.in
• 02.out