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

IvanZhang2009 · 2026-05-10 21:31:02 · 题解

为什么都在容斥？场上 0 分钟想到了一个 O(n^3) 状态的题意做法，四十分钟的时候就通过了，非常之好写。

首先 w_i 的限制告诉我们必须顺着 dp。然后显然要记录一下现在的值域信息。记 l_i 表示 [1\dots i] 前缀里最后一个有值的 p_i，只关心已经填的数值中比 l_i 小的个数。再记一维表示上一个数的值的大致位置即可。

我们令填进去的 <l_i 的数确定具体值，>l_i 的数只关心相对顺序。于是记 f_{i,j,k} 和 g_{i,j,k} 表示填了 p_1\dots p_i，有 j 个 <l_i 的值没被用过，f 的 k 表示 p_i\le l_i，且有 k 个空位比 p_i 小，g 的 k 表示 p_i>l_i，且在 >l_i 的数里相对位置排名为 k。

对于 p_i=0 转移很简单，是最朴素的前缀和优化。否则 l_i 改变，需要把 >l_{i-1} 的值选一部分放在 (l_{i-1},l_i) 内，直接枚举选几个数。这里把相对位置变成确定位置所以这是本题唯一的组合数。枚举量显然只有这个和 j，所以复杂度还是 O(n^3)。

做完了。代码懒得补了，反正超级好写。