문제 분류 수업 진도 대회 채점현황 순위 질문게시판
게임
스도쿠 타이핑 리듬 타자게임 타이핑 테트리스 타이핑 인베이더 타이핑 지뢰찾기 8192 공룡게임 타이핑 플래피버드 랭킹
로그인

5316 : B17 - 개구리 1 (경로 복원)

•시간제한: 2.000 S •메모리제한: 1024 MB •제출: 0 •통과: 0 •만든사람: suakii

5316 : B17 - 개구리 1 (경로 복원)

시간 2.000s · 메모리 1024MB · 제출 0 · 정답 0

문제 설명

$ 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$)
• 입력되는 모든 값은 정수입니다.。

입력 설명

첫 번째 줄에 발판의 개수 $ N $ 이 주어집니다.
두 번째 줄에 각 발판의 높이 $ h_i $ 가 공백으로 구분되어 주어집니다.

출력 설명

첫 번째 줄에 경로에 포함된 발판의 개수를 출력하십시오.
두 번째 줄에 경로상의 발판 번호를 순서대로 공백으로 구분하여 출력하십시오.

입력 예시
COPY
복사되었습니다!

4
10 30 40 20

출력 예시
COPY
복사되었습니다!

3
1 2 4

출처/분류

NOTICE  —  BFStudy OJ 정보샘
애들아, 문제 많이 풀고 게임 잠깐 하는거지?
— 정보샘