/ Vijos / 题库 /

抢美食

抢美食

时间限制:1秒  内存限制:256M


【题目描述】

  一条笔直好吃街上摆放着各种小吃!具体来说。一共摆放有 \(N\) 份美食,第 \(i\) 份美食的坐标为 \(X_i\)。小H一开始在坐标 \(S\) 处,每分钟可以向前或向后移动一个单位的距离。不过,美食暴露在空气中,其美味值每分钟会损失一个单位。

  作为吃货的小H当然要吃光所有的美食,但他也会在意美味的损失。请你告诉他该怎样来回移动,才能在美味损失之和最小的情况下消灭所有美食。

  注意,一般情况下,我们忽略小H吃的时间,因为他的进食速度很快。

【输入格式】

  第一行:两个整数:\(N\) 和 \(S\)。
  第二行到第 \(N+1\) 行:第 \(i+1\) 行有一个整数 \(X_i\),表示第 \(i\) 份美食的坐标。

【输出格式】

  一个整数,表示最小损失美味值之和。

【输入输出样例】

 Input

4 10
1
9
11
19

 Output

44

【输出样例解释】

  小H可以按下面的路线吃美食:
  时刻 0 在坐标 10 的位置;
  在时刻 1 走到坐标 9 的位置;
  在时刻 3 走到坐标 11 的位置;
  在时刻 11 走到坐标 19 的位置;
  在时刻 29 走到坐标 1 的位置;
  损失的美味值如下:1 + 3 + 11 + 29 = 44。可能也有其他路线使得损失的美味值相同,但没有那条路线会比 44 更小。

【数据限制】

  对于 \(100\%\) 的数据, \(1≤N≤1000\),\(1≤S,X_i≤1000000\)。

【来源】

  Mr.he

信息

ID
2228
难度
(无)
分类
动态规划 点击显示
标签
(无)
递交数
0
已通过
0
通过率
?
被复制
4
上传者