#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.