Marathon (Silver)
실버 II의견: 0
Bessie is enrolled in a running class, where she is eventually expected to run a marathon!
The marathon course consists of N checkpoints (3 <= N <= 500) to be visited in sequence, where checkpoint 1 is the start and checkpoint N is the finish. Bessie decides that she will skip up to K checkpoints (K < N) in order to shorten her total journey. She cannot skip checkpoints 1 or N.
Please help Bessie find the minimum distance that she has to run if she can skip up to K checkpoints. The distance between two checkpoints at (x1, y1) and (x2, y2) is the Manhattan distance |x1-x2| + |y1-y2|.
Line 1: The values of N and K.
Lines 2..1+N: Each line contains two space-separated integers, x and y, representing a checkpoint (-1000 <= x,y <= 1000), in the order they must be visited.
The minimum distance that Bessie can run by skipping up to K checkpoints.
marathon.inmarathon.out5 2
0 0
8 3
1 1
10 -5
2 24Output details: Skipping the checkpoints at (8, 3) and (10, -5) leads to a minimum total distance of 4.
riseoj 작성
출처 올림피아드 > USACO > 2014-2015 > December > Silver
평가 및 의견
Marathon (Silver)
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Marathon (Silver)