#PU492. USACO 2014 December Contest, Silver — Problem 2. Marathon
USACO 2014 December Contest, Silver — Problem 2. Marathon
USACO 2014 December Contest, Silver — Problem 2. Marathon
题目描述
Problem 2: Marathon [Nick Wu, 2014]
Unhappy with the poor health of his cows, Farmer John enrolls them in
an assortment of different physical fitness activities. His prize cow
Bessie is enrolled in a running class, where she is eventually
expected to run a marathon through the downtown area of the city near
Farmer John's farm!
The marathon course consists of N checkpoints (3 <= N <= 500) to be
visited in sequence, where checkpoint 1 is the starting location and
checkpoint N is the finish. Bessie is supposed to visit all of these
checkpoints one by one, but being the lazy cow she is, she 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, however, since
that would be too noticeable.
Please help Bessie find the minimum distance that she has to run if
she can skip up to K checkpoints.
Since the course is set in a downtown area with a grid of streets, the
distance between two checkpoints at locations (x1, y1) and (x2, y2) is
given by |x1-x2| + |y1-y2|.
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
5 2
0 0
8 3
1 1
10 -5
2 2
4
提示
several checkpoints occurring at the same physical location. When
Bessie skips such a checkpoint, she only skips one instance of the
checkpoint -- she does not skip every checkpoint occurring at the same
location.