[Usaco2007 Demo]Grazing on the Run

题目描述

A long, linear field has N (1 <= n="" <="1,000)" clumps="" of="" grass="" at="" unique="" integer="" locations="" on="" what="" will="" be="" treated="" as="" a="" number="" line.="" think="" the="" points="" bessie="" starts="" some="" specified="" location="" l="" line="" (1="" and="" traverses="" in="" two="" possible="" directions="" (sometimes="" reversing="" her="" direction)="" order="" to="" reach="" eat="" all="" clumps.="" she="" moves="" constant="" speed="" (one="" unit="" distance="" one="" time),="" eats="" clump="" instantly="" when="" encounters="" it.="" that="" aren't="" eaten="" for="" while="" get="" stale.="" we="" say="" ``staleness''="" is="" amount="" time="" elapses="" from="" moving="" until="" clump.="" wants="" minimize="" total="" staleness="" eats.="" find="" minimum="" can="" achieve="" eating="" p="">

---

输入格式

* Line 1 : Two space-separated integers: N and L. * Lines 2..N+1: Each line contains a single integer giving the position P of a clump (1 <= p="" <="1,000,000).">

---

输出格式

* Line 1: A single integer: the minimum total staleness Bessie can achieve while eating all the clumps.

---

样例输入

4 10
1
9
11
19

INPUT DETAILS:

Four clumps: at 1, 9, 11, and 19. Bessie starts at location 10.

---

样例输出

44

OUTPUT DETAILS:

Bessie can follow this route:

* start at position 10 at time 0
* move to position 9, arriving at time 1
* move to position 11, arriving at time 3
* move to position 19, arriving at time 11
* move to position 1, arriving at time 29

giving her a total staleness of 1+3+11+29 = 44.  There are other routes
with the same total staleness, but no route with a smaller one.

---

提示

没有写明提示

---

题目来源

Gold