题解

思路

从支撑链看结构

每块紫色积木都对应一条从高度 $h$ 走到地面的支撑链。相邻两层中，链的横坐标至多变化 $1$。两条链一旦合并，继续向下共用同一批积木不会变差。

设 $f(l,r)$ 表示支撑第 $l$ 至第 $r$ 块紫色积木所需的最少额外积木数。单独一条链需要 $h$ 块，因此 $f(i,i)=h$。

区间转移

考虑把区间 $[l,r]$ 最后分成 $[l,m]$ 与 $[m+1,r]$。两侧最外端的支撑链每下降一层至多相向移动 $2$ 个横坐标单位。令

$$c(l,r)=\max\left(0,h+1-\left\lceil\frac{x_r-x_l}{2}\right\rceil\right).$$

两部分最多可以在最底部共享 $c(l,r)$ 块积木，于是

$$f(l,r)=\min_{l\le m<r}\bigl(f(l,m)+f(m+1,r)-c(l,r)\bigr).$$

反过来，在任意最优结构中，选择相邻支撑链首次分开的最低位置，也会得到上述某个分割；端点距离限制说明共享高度不可能超过 $c(l,r)$，所以转移既可达又是下界。

若同层出现横坐标相差 $1$ 的两块积木，可把其中一块向外平移一格而不增加数量，因此允许链暂时重叠的递推不会破坏“不相交”的要求。

做法

按区间长度从小到大枚举 $[l,r]$，预先由端点横坐标计算可共享高度，再枚举分割点 $m$ 完成转移。

子任务

• $h=0$ 时所有紫色积木已经接触地面，答案为 $0$。
• $h=1$ 时只需贪心扫描；横坐标相差 $2$ 的相邻紫色积木可共用一块支撑积木。
• 满分算法按区间长度计算上述动态规划。

复杂度

时间复杂度为 $O(n^3)$，空间复杂度为 $O(n^2)$。