P9054

· · 题解

咋没人做，气抖冷！

可以发现，原最短路一定是数组里最小的元素 d，或 d+1，或 d+2，不妨枚举原最短路长度 D。

难点在于决定哪些为 D 的元素真的在最短路上，每个这样的元素需要吞掉旁边的一个非最短路元素，其它真实在最短路上的元素 x 会吞掉至少 x-D+1 个元素，且可以证明吞掉的元素要么是一个区间，要么至多有一个元素与其它元素的区间距离为 2。因此，只要剩下的未被吞掉元素连续段除以二下取整长度和 \ge 需要的最短路元素个数，就能构造出方案。这里可以用简单的线性 dp 求出连续段除以二下取整长度和的最大值。

最后枚举 1,n 的位置，可以发现要么是最短路元素要么距离为常数，所以是 O(n) 种情况，并合并 dp 值。dp 时需要注意 1,n 位置之间的边界，以及序列两边的边界情况。

根据 dp 值构造方案也是 trivial 的，只需倒推每个最短路元素吞掉了哪些元素，得到必要的大小关系并拓扑排序。综上，本题在 O(n) 时间复杂度内得到解决。