5316 : B17 - 개구리 1 (경로 복원)
•시간제한: 2.000 S
•메모리제한: 1024 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
$ N $ 개의 발판이 있습니다. 발판에는 $ 1, 2, \dots, N $ 의 번호가 매겨져 있습니다. 각 $ i $ ($ 1 \le i \le N $)에 대해 발판 $ i $ 의 높이는 $ h_i $ 입니다.
처음에 발판 $ 1 $ 에 개구리가 있습니다. 개구리는 다음 행동을 반복하여 발판 $ N $ 까지 가려고 합니다.
발판 $ i $ 에 있을 때, 발판 $ i+1 $ 또는 $ i+2 $ 로 점프합니다. 이때 점프할 발판을 $ j $ 라고 하면 비용 $|h_i - h_j|$ 를 지불합니다.
개구리가 발판 $ N $ 에 도달하기까지 지불하는 비용의 합이 최소가 되는 이동 경로를 하나 출력하는 프로그램을 작성하십시오.
[제약 조건]
• $2 ≤ N ≤ 100\,000$
• $1 ≤ h_i ≤ 10\,000$ ($1 ≤ i ≤ N$)
• 입력되는 모든 값은 정수입니다.。
처음에 발판 $ 1 $ 에 개구리가 있습니다. 개구리는 다음 행동을 반복하여 발판 $ N $ 까지 가려고 합니다.
발판 $ i $ 에 있을 때, 발판 $ i+1 $ 또는 $ i+2 $ 로 점프합니다. 이때 점프할 발판을 $ j $ 라고 하면 비용 $|h_i - h_j|$ 를 지불합니다.
개구리가 발판 $ N $ 에 도달하기까지 지불하는 비용의 합이 최소가 되는 이동 경로를 하나 출력하는 프로그램을 작성하십시오.
[제약 조건]
• $2 ≤ N ≤ 100\,000$
• $1 ≤ h_i ≤ 10\,000$ ($1 ≤ i ≤ N$)
• 입력되는 모든 값은 정수입니다.。
입력 설명
첫 번째 줄에 발판의 개수 $ N $ 이 주어집니다.
두 번째 줄에 각 발판의 높이 $ h_i $ 가 공백으로 구분되어 주어집니다.
두 번째 줄에 각 발판의 높이 $ h_i $ 가 공백으로 구분되어 주어집니다.
출력 설명
첫 번째 줄에 경로에 포함된 발판의 개수를 출력하십시오.
두 번째 줄에 경로상의 발판 번호를 순서대로 공백으로 구분하여 출력하십시오.
두 번째 줄에 경로상의 발판 번호를 순서대로 공백으로 구분하여 출력하십시오.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
4
10 30 40 20
출력 예시
COPY
복사되었습니다!
복사되었습니다!
3
1 2 4