5220 : A21 - 블록 게임
•시간제한: 2.000 S
•메모리제한: 1024 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
$N$ 개의 블록이 나열되어 있으며, 왼쪽부터 순서대로 1, 2, $\dots$ , $N$ 번 번호가 매겨져 있습니다.
당신은 아래 2가지 조작을 여러 번 수행하여 모든 블록을 제거하려 합니다.
블록 $i$ ($i = 1, 2, \dots, N$)를 블록 $P_i$ 보다 먼저 제거한 경우 $A_i$ 점을 얻습니다.
얻을 수 있는 총점의 최댓값을 구하는 프로그램을 작성하십시오.
[제약 조건]
• $2 \le N \le 2000$
• $1 \le P_i \le N$
• $P_i \neq i$
• $1 \le A_i \le 100$
• 입력되는 모든 값은 정수입니다.
당신은 아래 2가지 조작을 여러 번 수행하여 모든 블록을 제거하려 합니다.
- 현재 남아 있는 블록 중 가장 왼쪽의 블록을 제거한다.
- 현재 남아 있는 블록 중 가장 오른쪽의 블록을 제거한다.
블록 $i$ ($i = 1, 2, \dots, N$)를 블록 $P_i$ 보다 먼저 제거한 경우 $A_i$ 점을 얻습니다.
얻을 수 있는 총점의 최댓값을 구하는 프로그램을 작성하십시오.
[제약 조건]
• $2 \le N \le 2000$
• $1 \le P_i \le N$
• $P_i \neq i$
• $1 \le A_i \le 100$
• 입력되는 모든 값은 정수입니다.
입력 설명
첫째 줄에 $N$ 이 주어집니다.
다음 $N$ 개 줄에 각 블록의 $P_i$ 와 $A_i$ 가 공백으로 구분되어 주어집니다.
다음 $N$ 개 줄에 각 블록의 $P_i$ 와 $A_i$ 가 공백으로 구분되어 주어집니다.
출력 설명
얻을 수 있는 총점의 최댓값을 출력하십시오.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
4
4 20
3 30
2 40
1 10
출력 예시
COPY
복사되었습니다!
복사되었습니다!
60