Vittorio Plays with LEGO Bricks

题目描述

Vittorio is playing with his new LEGO Duplo bricks. All the bricks have the shape of a square cuboid with a $ 2 \times 2 $ square base and a height of $ 1 $ . They can be arranged in the 3D space to build structures, provided that the following rules are met: 1. No two bricks can intersect, but they can touch on their faces. 2. The corners of every brick must have integer coordinates (so bricks are axis-aligned) and the $ z $ coordinates of all corners must be non-negative. 3. The square bases of every brick must be parallel to the ground (i.e. the plane $ z=0 $ ). 4. The lower base of any brick that is not touching the ground must touch the upper base of some other brick in a region of positive area (when this happens, the two bricks stay attached to each other thanks to small studs). For example, this is a valid structure: Vittorio wants to build a structure that includes purple bricks in the following $ n $ positions: $ (x_1, 0, h) $ , $ (x_2, 0, h) $ , $ \dots $ , $ (x_n, 0, h) $ — these are the coordinates of the centers of their lower bases; note that all of these bricks have $ y $ coordinate equal to $ 0 $ and $ z $ coordinate equal to $ h $ . Vittorio will use additional bricks of other colors to support the purple bricks. He is willing to place bricks only in positions where the center of the lower base has $ y $ coordinate equal to $ 0 $ . What is the minimum number of additional bricks needed? It can be shown that a valid construction always exists.

输入输出格式

输入格式

The first line contains two integers $ n $ and $ h $ ( $ 1 \le n \le 300 $ , $ 0 \le h \le 10^9 $ ) — the number of purple bricks and their common $ z $ coordinate. The second line contains $ n $ integers $ x_1, \, x_2, \, \dots, \, x_n $ ( $ 1 \le x_i \le 10^9 $ , $ x_i + 1 < x_{i+1} $ ) — the $ x $ coordinates of the purple bricks (centers of the bases), given in increasing order.

输出格式

Print the minimum number of additional bricks needed.

输入输出样例

输入样例 #1

4 0
2 7 11 13

输出样例 #1

0

输入样例 #2

4 1
2 7 11 13

输出样例 #2

3

输入样例 #3

4 100
2 7 11 13

输出样例 #3

107

输入样例 #4

4 3
2 5 8 11

输出样例 #4

8

说明

In the first sample, all the purple bricks lie on the ground, so no additional bricks are needed. In the second sample, Vittorio will have to place supporting bricks under the purple bricks, and he can use a single brick to support both the third and the fourth purple bricks. For example, he can place additional bricks at positions $ (3, 0, 0) $ , $ (7, 0, 0) $ and $ (12, 0, 0) $ . It can be shown that it is impossible to build a valid construction using less than $ 3 $ additional bricks. In the fourth sample, a possible structure that minimizes the number of additional bricks is shown in the problem description.

**维托里奥玩积木**

**题目描述：**
维托里奥正在玩他的新乐高积木。所有积木的形状都是底面为 $2 \times 2$ 平方立方体，高度为 $1$。它们可以在三维空间中排列来建造结构，必须满足以下规则：

1. 任意两个积木不能相交，但它们可以在它们的面上接触。
2. 每个积木的角必须具有整数坐标（即积木与坐标轴平行），所有角的 $z$ 坐标必须为非负。
3. 每个积木的方形底面必须与地面平行（即平面 $z=0$）。
4. 任何不接触地面的积木的下底必须与某个其他积木的上底在正面积区域接触（当这种情况发生时，两个积木通过小凸起连接在一起）。

例如，这是一个有效的结构：


维托里奥想要建造一个结构，其中包括在以下 $n$ 位置的紫色积木：$(x_1, 0, h)$, $(x_2, 0, h)$, ..., $(x_n, 0, h)$ —— 这些是它们下底的中心的坐标；注意，所有这些积木的 $y$ 坐标都等于 $0$ 且 $z$ 坐标等于 $h$。维托里奥将使用其他颜色的额外积木来支撑紫色积木。他只愿意在底面中心 $y$ 坐标等于 $0$ 的位置放置积木。需要多少额外的积木？

可以证明，总是存在一个有效的建造方法。

**输入输出格式：**

**输入格式：**
第一行包含两个整数 $n$ 和 $h$（$1 \le n \le 300$, $0 \le h \le 10^9$）—— 紫色积木的数量和它们的公共 $z$ 坐标。

第二行包含 $n$ 个整数 $x_1, x_2, \dots, x_n$（$1 \le x_i \le 10^9$, $x_i + 1 < x_{i+1}$）—— 紫色积木的 $x$ 坐标（底面中心），按递增顺序给出。

**输出格式：**
输出所需的最少额外积木数量。

**输入输出样例：**

**输入样例 #1**
```
4 0
2 7 11 13
```
**输出样例 #1**
```
0
```

**输入样例 #2**
```
4 1
2 7 11 13
```
**输出样例 #2**
```
3
```

**输入样例 #3**
```
4 100
2 7 11 13
```
**输出样例 #3**
```
107
```

**输入样例 #4**
```
4 3
2 5 8 11
```
**输出样例 #4**
```
8
```

**说明：**
在第一个样例中，所有紫色积木都放在地面上，所以不需要额外的积木。

在第二个样例中，维托里奥必须在紫色积木下放置支撑积木，并且他可以用一个积木来支撑第三和第四个紫色积木。例如，他可以在位置 $(3, 0, 0)$, $(7, 0, 0)$ 和 $(12, 0, 0)$ 放置额外的积木。可以证明，使用少于 $3$ 个额外积木建造有效的结构是不可能的。

在第四个样例中，问题描述中展示了一个可能的结构，该结构最小化了额外积木的数量。**维托里奥玩积木** **题目描述：** 维托里奥正在玩他的新乐高积木。所有积木的形状都是底面为 $2 \times 2$ 平方立方体，高度为 $1$。它们可以在三维空间中排列来建造结构，必须满足以下规则： 1. 任意两个积木不能相交，但它们可以在它们的面上接触。 2. 每个积木的角必须具有整数坐标（即积木与坐标轴平行），所有角的 $z$ 坐标必须为非负。 3. 每个积木的方形底面必须与地面平行（即平面 $z=0$）。 4. 任何不接触地面的积木的下底必须与某个其他积木的上底在正面积区域接触（当这种情况发生时，两个积木通过小凸起连接在一起）。 例如，这是一个有效的结构：  维托里奥想要建造一个结构，其中包括在以下 $n$ 位置的紫色积木：$(x_1, 0, h)$, $(x_2, 0, h)$, ..., $(x_n, 0, h)$ —— 这些是它们下底的中心的坐标；注意，所有这些积木的 $y$ 坐标都等于 $0$ 且 $z$ 坐标等于 $h$。维托里奥将使用其他颜色的额外积木来支撑紫色积木。他只愿意在底面中心 $y$ 坐标等于 $0$ 的位置放置积木。需要多少额外的积木？ 可以证明，总是存在一个有效的建造方法。 **输入输出格式：** **输入格式：** 第一行包含两个整数 $n$ 和 $h$（$1 \le n \le 300$, $0 \le h \le 10^9$）—— 紫色积木的数量和它们的公共 $z$ 坐标。 第二行包含 $n$ 个整数 $x_1, x_2, \dots, x_n$（$1 \le x_i \le 10^9$, $x_i + 1 < x_{i+1}$）—— 紫色积木的 $x$ 坐标（底面中心），按递增顺序给出。 **输出格式：** 输出所需的最少额外积木数量。 **输入输出样例：** **输入样例 #1** ``` 4 0 2 7 11 13 ``` **输出样例 #1** ``` 0 ``` **输入样例 #2** ``` 4 1 2 7 11 13 ``` **输出样例 #2** ``` 3 ``` **输入样例 #3** ``` 4 100 2 7 11 13 ``` **输出样例 #3** ``` 107 ``` **输入样例 #4** ``` 4 3 2 5 8 11 ``` **输出样例 #4** ``` 8 ``` **说明：** 在第一个样例中，所有紫色积木都放在地面上，所以不需要额外的积木。 在第二个样例中，维托里奥必须在紫色积木下放置支撑积木，并且他可以用一个积木来支撑第三和第四个紫色积木。例如，他可以在位置 $(3, 0, 0)$, $(7, 0, 0)$ 和 $(12, 0, 0)$ 放置额外的积木。可以证明，使用少于 $3$ 个额外积木建造有效的结构是不可能的。 在第四个样例中，问题描述中展示了一个可能的结构，该结构最小化了额外积木的数量。