← 返回题目列表

Codeforces · 1776/B

B. 维托里奥玩乐高积木

中文机器翻译题面 查看原题

维托里奥正在玩他的新乐高得宝积木。所有砖块的形状均为正方形长方体,底面为 $$$2 \times 2$$$ 方形,高度为 $$$1$$$。它们可以在 3D 空间中排列来构建结构,前提是满足以下规则:

1. 没有两块砖可以相交,但它们的面可以接触。
2. 每个砖块的角点必须具有整数坐标(因此砖块是轴对齐的),并且所有角点的 $$$z$$$ 坐标必须为非负数。
3. 每块砖块的方形底面必须与地面平行(即平面 $$$z=0$$$)。
4. 任何不接触地面的砖块的下底必须接触正面积区域中其他砖块的上底(当发生这种情况时,由于小螺柱,两块砖保持相互连接)。

例如,这是一个有效的结构:

Vittorio 想要建造一个在以下 $$$n$$$ 位置包含紫色砖块的结构:$$$(x_1, 0, h)$$$, $$$(x_2, 0, h)$$$, $$$\dots$$$, $$$(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

注意

在第一个示例中,所有紫色砖块都位于地面上,因此不需要额外的砖块。

在第二个示例中,Vittorio 必须在紫色砖块下方放置支撑砖块,并且他可以使用一块砖块来支撑第三个和第四个紫色砖块。例如,他可以在位置 $$$(3, 0, 0)$$$、$$$(7, 0, 0)$$$ 和 $$$(12, 0, 0)$$$ 放置额外的砖块。可以证明,使用少于 $$$3$$$ 的额外砖块来建造有效的结构是不可能的。

在第四个示例中,问题描述中显示了最小化附加砖块数量的可能结构。