My Blogs
P10432 [JOISC 2024 Day1] 滑雪 2
感觉是挺好的观察性质题，vp 的时候场切了。
首先酒店一定是建在最低的某一个点。把高度离散化之后，把点扔到对应的位置。可以发现高度为 $i$ 的层的所有点，如果能接上一层的连接器那一定会尽量接上（因为到了下一层它本身也可以贡献一个空的连接器）。
设 $v_i$ 是高度为 $i$ 的点里最小的 $C$，则从 $1\sim i$ 的高度中选择一个搭连接器的代价就是 $\min_{1\leq j\leq i} v_j$。原因很简单，$i-1$ 层一定会有若干个未用的连接器，相同情况下肯定是对 $C$ 较大的对他进行升高高度的操作，所以 $C$ 最小的一定会留在当前层。
这样就可以 DP 了。设 $f_{i,j,k}$ 表示当前高度在第 $i$ 层，前 $i-1$ 层有 $j$ 个连接器可用，并且有 $k$ 个高度小于 $i$ 的点的高度被加到了 $i$ 的最小代价。
假设当前层有 $x$ 个点，直接把每个 $k$ 加上 $x$ 即可。转移可以从 $1\sim i-1$ 新建一个连接器上来转移到 $f_{i,j+1,k}$，可以不再新建直接往下转移到 $f_{i+1,j,\max(0,k-(h_{i+1}-h_i-1)\times j)}$。总复杂度是 $\mathcal O(n^3)$。
有一个小细节，因为 $i$ 层加连接器的时候只能从前 $i-1$ 层建，所以离散化的数组里不仅需要有 $h_j$，还应有 $h_{j+1}$。代码找不到了 QwQ。