5234 : A35 - 게임 4
•시간제한: 2.000 S
•메모리제한: 1024 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
아래 그림과 같은 $N$ 단의 피라미드가 있으며, 최하단에는 왼쪽부터 순서대로 정수 $A_1, A_2, \dots, A_N$ 이 적혀 있습니다. 또한 최상단에는 하나의 말이 놓여 있습니다.
타로와 지로는 이 피라미드를 사용하여 게임을 합니다. 말이 최하단에 도달할 때까지 각 플레이어는 교대로 다음 조작 중 하나를 수행합니다 (타로가 선공입니다).
게임 종료 시 말의 위치에 적힌 정수를 점수라고 합니다. 타로는 점수를 최대화하려 하고, 지로는 점수를 최소화하려 할 때, 최종 점수는 얼마가 됩니까?
[제약 조건]
• 입력되는 모든 값은 정수입니다.
• $2 \le N \le 2000$
• $1 \le A_i \le 100000$
타로와 지로는 이 피라미드를 사용하여 게임을 합니다. 말이 최하단에 도달할 때까지 각 플레이어는 교대로 다음 조작 중 하나를 수행합니다 (타로가 선공입니다).
- 말을 왼쪽 아래 방향으로 한 칸 이동시킨다.
- 말을 오른쪽 아래 방향으로 한 칸 이동시킨다.
게임 종료 시 말의 위치에 적힌 정수를 점수라고 합니다. 타로는 점수를 최대화하려 하고, 지로는 점수를 최소화하려 할 때, 최종 점수는 얼마가 됩니까?
[제약 조건]
• 입력되는 모든 값은 정수입니다.
• $2 \le N \le 2000$
• $1 \le A_i \le 100000$
입력 설명
첫째 줄에 $N$ 이 주어집니다.
둘째 줄에 $A_1, A_2, \dots, A_N$ 이 공백으로 구분되어 주어집니다.
둘째 줄에 $A_1, A_2, \dots, A_N$ 이 공백으로 구분되어 주어집니다.
출력 설명
최종 점수를 출력하십시오.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
4
20 10 30 40
출력 예시
COPY
복사되었습니다!
복사되었습니다!
30