레이팅 미적용설명
베시는 달리기 수업에 등록했고, 최종적으로는 마라톤을 완주해야 한다!
마라톤 코스는 순서대로 방문해야 하는 N개의 체크포인트로 이루어져 있다 (3 <= N <= 500). 체크포인트 1이 출발점이고 체크포인트 N이 결승점이다. 베시는 전체 여정을 줄이기 위해 최대 K개의 체크포인트를 건너뛰기로 한다 (K < N). 체크포인트 1과 N은 건너뛸 수 없다.
최대 K개의 체크포인트를 건너뛸 수 있을 때 베시가 달려야 하는 최소 거리를 구하시오. (x1, y1)과 (x2, y2)에 있는 두 체크포인트 사이의 거리는 맨해튼 거리 |x1-x2| + |y1-y2|이다.
제약
입력 형식
첫째 줄에 N과 K가 주어진다.
둘째 줄부터 1+N번째 줄까지 각 줄에 공백으로 구분된 두 정수 x와 y가 주어지며, 이는 체크포인트를 나타낸다 (-1000 <= x,y <= 1000). 체크포인트는 방문해야 하는 순서대로 주어진다.
출력 형식
최대 K개의 체크포인트를 건너뛸 때 베시가 달릴 수 있는 최소 거리를 출력한다.
Standard input / output
This problem is judged over standard input/output. The original contest used named files — if you prefer the classic interface, tick “File I/O” on the submit form and read/write these files instead:
입력을 읽을 파일
marathon.in · 출력을 쓸 파일 marathon.out예제 1
입력
5 2
0 0
8 3
1 1
10 -5
2 2출력
4설명
Output details: Skipping the checkpoints at (8, 3) and (10, -5) leads to a minimum total distance of 4.
문제 정보
riseoj 작성
출처 올림피아드 > USACO > 2014-2015 > December > Silver
태그