猫咪锻炼题解

思路推导

对排列建立最大笛卡尔树：树满足中序遍历顺序与塔的左右顺序相同，并且父节点高度大于子节点。根节点正是高度为 $N$ 的塔。

对于任意节点 $u$，其子树恰好对应一个连续区间，且 $u$ 是区间内最高的塔。当猫位于 $u$ 且当前可达范围是这整个区间时，移除 $u$ 后，猫下一步只可能进入左子树或右子树中最高的塔，也就是 $u$ 的左儿子或右儿子。通过预先移除另一侧不需要的塔，可以实现任意一个存在的儿子转移。

因此，问题转化为从笛卡尔树根出发，选择一条向下路径，使相邻节点编号差之和最大。

做法

使用单调递减栈从左到右构造最大笛卡尔树。处理位置 $i$ 时，不断弹出高度小于 $P_i$ 的栈顶；最后弹出的节点成为 $i$ 的左儿子，弹栈后新的栈顶（若存在）把 $i$ 设为右儿子。

随后按后序计算：节点 $u$ 的答案等于左儿子答案加编号距离、右儿子答案加编号距离二者的最大值；不存在的方向贡献为零。根节点的值即为答案。

正确性证明

笛卡尔树任一节点的子树对应连续区间，且该节点是区间最高塔。猫处于该节点时，移除它后，两侧剩余可达部分中最高的塔分别是其左右儿子，因此任何有效下一次移动都可归约为走向某个儿子。

反过来，对于任一存在的儿子，可以先移除不需要方向以及边界外的塔，再移除当前塔，使猫移动到该儿子。因此树上的每条向下路径都存在对应的移除方案。

动态规划枚举当前节点的两个可能儿子，并取总距离较大者，恰好得到从该节点开始的最优路径。由树上归纳，根节点的结果就是全局最优答案。

复杂度分析

每个节点至多入栈、出栈一次，动态规划也只访问每条树边一次。时间复杂度为 $O(N)$，空间复杂度为 $O(N)$。