题解：P16433 [APIO 2026 中国赛区] 上升

szh_AK_all · 2026-05-13 22:13:58 · 题解

很显然是排列 dp。

容易发现，我们要维护这个 dp，必须要知道已经填的数的相对大小关系，或者说是在转移过程中可以间接的确定数与数之间的相对大小关系。令 l_i 表示满足 p_j\ne 0 且 j\le i 的最大的 j，对于当前填了的 \le p_{l_i} 的数，我们可以在转移过程中确定他们具体填多少；而对于填了的 >p_{l_i} 的数，则需要知道这些数之间的相对顺序，在下一个数值确定的位置再确定他们具体填多少。于是设 f_{i,j,k} 表示填了前 i 个位置，有 j 个 \le p_{l_i} 的数没填且 a_i\le p_{l_i}，有 k 个 <a_i 的数没填时的答案；设 g_{i,j,k} 表示填了前 i 个位置，有 j 个 \le p_{l_i} 的数没填且 a_i> p_{l_i}，a_i 在填了的 >p_{l_i} 的数中排名为 k 时的答案。

具体的，一个确定的数 p_i 会作为一部分 \le p_i 的数的分界线。在 i 之前，我们间接知道这些数的相对顺序，但不知道他们具体填什么，在转移到 i 时，依然知道 p_i 的排名，也确定了在该排名上填的数具体就是 p_i，此时我们需要确定这一部分数到底填什么；而在位置 i 之后，我们就能知道另一部分 \le p_i 的数具体怎么填。

再进一步可以发现，在 i 这个位置我们要确定在此前填了的在 (p_{l_{i-1}}+1)\sim(p_i-1) 范围内的数的具体数值，由于 p_i 恰好比这些数大，所以 g_{i,j,k} 的状态 k 就确定了该范围内的数的个数，方案数即为 C_{p_i-1-p_{l_{i-1}}}^{k-1}。

于是转移的大体思路就确定了。转移时，用已知的 f,g 值去更新别的值会比较好写一点。具体的，我们要考虑：

这六种情况，每次可以转移到的是一段 k 连续的 dp 值，于是可以前缀和优化，做到 O(n^3)。f,g 的状态设计恰好让转移比较好写。

当位置 i+1 本身就确定了值时，我们先平凡的求出 g 数组，因为 p_{i+1}>p_{l_i}，然后利用 g 数组与延迟计算的组合系数转移给 f 数组，转移后 g 数组是没有值的，结合定义可知。