题解

思路

1. 预处理

山的难度只会增加。因此 $s_i<d$ 的登山者永远不能登山，可以直接删去。对于其余登山者，若 $a_i\le d$，无论何时先让他登山都不会提高初始难度，所以这些人都可以计入答案。记人数为 base。

剩余登山者均满足 $s_i\ge d$ 且 $a_i>d$。按 $a_i$ 非降序排列，并增加虚拟状态 $0$：$a_0=d,dp_0=\text{base}$。

做法

2. 子任务 1：子集状态搜索

选定一个集合后，当前难度只由集合中最大的 $a_i$ 决定，与具体顺序无关。令 reachable[mask] 表示能否按某种顺序恰好让集合 mask 登山。枚举一个未选的人，只要他的 $s_i$ 不小于当前难度就能转移。

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

3. 子任务 2：二次动态规划

把会使难度达到 $a_i$ 的登山者称为一个“锚点”。固定上一个锚点 $j<i$ 后，在 $j$ 与 $i$ 之间，凡是满足 $s_k\ge a_i$ 的登山者都可以在难度升到 $a_i$ 后登山而不再提高难度。锚点 $i$ 自身能接在 $j$ 后，当且仅当 $a_j\le s_i$。

于是

$$dp_i=1+\max_{0\le j<i,\ a_j\le s_i} \left(dp_j+\#\{k\mid j<k<i,\ s_k\ge a_i\}\right).$$

对每个 $i$ 从右向左枚举 $j$，同时维护大括号内的计数，即可在 $O(n^2)$ 时间、$O(n)$ 空间内求解。

该递推不会漏解：任意最优顺序可把不提高当前难度的人移动到相邻两个锚点之间；反过来，每次转移中的中间登山者都满足技巧条件，按上述顺序确实可行。

4. 子任务 3：线段树优化

处理第 $i$ 个状态时，在线段树位置 $j$ 保存

$$dp_j+\#\{k\mid j<k<i,\ s_k\ge a_i\}.$$

由于 $a_i$ 非降：

• 新加入中间区间的登山者 $k=i-1$ 若满足 $s_k\ge a_i$，会给所有 $j<k$ 的位置贡献 $1$，即区间 $[0,k-1]$ 加一；
• 当阈值升高到 $a_i$ 时，所有 $s_k<a_i$ 的旧贡献失效，各自在 $[0,k-1]$ 减一；用按 $s_k$ 排序的小根堆维护即可；
• 合法前驱是 $a_j\le s_i$ 的前缀。二分得到其最右位置，查询前缀最大值，再把 $dp_i$ 单点写入线段树。

每位登山者只进出堆一次，每次修改或查询为 $O(\log n)$。总复杂度为 $O(n\log n)$，空间复杂度为 $O(n)$。

复杂度

三层算法的时间复杂度依次为 $O(n2^n)$、$O(n^2)$、$O(n\log n)$；空间复杂度依次为 $O(2^n)$、$O(n)$、$O(n)$。

5. 正确性要点

预处理只删除永远不可行的人，并提前选择不会提高初始难度的人。递推按最后两个锚点分解规范化后的最优顺序，中间计数恰好包含所有可在新难度下无害登山的人。线段树维护的值与二次递推完全相同，只把逐项计数改为区间加减与前缀最大值，因此最终最大 dp 即为答案。