P10789 [NOI2024] 登山 题解

首先基本确定本题是计数 dp，但向上冲刺时有许多限制

观察到向上冲刺到的节点深度在一个范围，这个比较好处理，记为限制 1。接着有一个猎奇限制 2，也是限制向上冲刺到的节点深度，但是和先前的登山序列有关，直接做好像只能状压，不优美

于是考虑限制 2 有什么性质，我们可以考虑把限制简化，最好单独分开。注意到有 \(0 \le h_i < d_i\)，可以从这里撕开一条口子

首先向上跳的过程中，\(d_i\) 递减，为了满足限制，跳到 \(i\) 时，\(i\) 下面的节点 \(j\) 的 \(d_j-h_j > d_i\)，接着从 \(i\) 跳到 \(k\)，则有 \(d_i-h_i > d_k\) 且 \(d_j-h_j > d_k\)，又因为 \(d_i > d_k\)，所以 \(d_j-h_j > d_k\) 这个条件一定满足，故只用考虑 \(d_i-h_i > d_k\) 的情况

所以我们向上冲刺到 \(k\)，限制 2 转化为上一次冲刺的点到现在的限制，这样就没有后效性，可以 dp

我们设 \(f_i\) 表示从 \(i\) 走到 \(1\) 的方案，那么我们可以向上跳也可以往下走，考虑只向上跳一次到 \(k\)，直接用 \(dp_k\) 的答案，则还需枚举向下走的 \(j\)，则有一个 \(O(n^3)\) 的 dp，注意到 \(k\) 在一个区间内，可以维护 dp 数组的前缀和，优化到 \(O(n^2)\)

然后正解我还不会