CF1776B Vittorio Plays with LEGO Bricks
题目描述
Vittorio 正在玩他的新 LEGO Duplo 积木。所有积木都是底面为 $2 \times 2$ 的正方体长方体，高为 $1$。它们可以在三维空间中搭建结构，但需要满足以下规则：
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$。Vittorio 可以使用其他颜色的积木来支撑紫色积木。他只愿意把积木放在下底面中心 $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$ 坐标（底面中心），按递增顺序给出。
输出格式
输出所需的最少额外积木数量。
说明/提示
在第一个样例中，所有紫色积木都在地面上，因此不需要额外的积木。
在第二个样例中，Vittorio 需要在紫色积木下方放置支撑积木，并且可以用一个积木同时支撑第三个和第四个紫色积木。例如，他可以在 $(3, 0, 0)$、$(7, 0, 0)$ 和 $(12, 0, 0)$ 处放置额外积木。可以证明，无法用少于 $3$ 个额外积木搭建出合法结构。
在第四个样例中，最少额外积木的搭建方式如题目描述中的图片所示。
由 ChatGPT 4.1 翻译