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

EricWan · 2026-05-11 16:06:41 · 题解

蒸了 3.5h 终于过了，获得了金牌守门员。

一看就是贡献延后计算，但是很多种状态的定义方法都会写到最后发现假了，这里直接说状态的定义，思维过程我也无法写出因为我赛时在不断假。

在序列开头补充一个固定的数值 1，把后面所有数值和位置平移 1，在结尾加入 n+2，变成 1,2,\dots,n+2 的排列，定义 l_i 为 i 左边第一个确定的数，这样 l_i 一定是有定义的。将 n 增加 2。

定义 f_{i,j,k} 为第 i 个数小于 l_i，前 i 个数已经确定完了，还有 j 个小于 l_i 的数值没有被填充，还有 k 个小于 a_i 的数没有被填充的所有方案的前 i-1 个 w 作出的贡献。

定义 g_{i,j,k} 为第 i 个数大于等于 l_i，前 i 个数已经确定完了，还有 j 个小于 l_i 的数值没有被填充，a_i 在前面所有大于 l_i 的数中是第 k 小的。

这个状态的定义看起来很没道理，但是随着写转移方程我只能找到这一个合理的定义。

初始化 f_{1,0,1}=1，答案是 g_{n,0,1}。

先想想怎样从上一个位置转移到锁定元素。容易发现 l_{i+1}=a_{i+1}，所以必定会转移到 g_{i+1,free_{new},1}。具体的，枚举当前的 g_{i,j,k} 在转移后有多少个大于 l_i 的数变成了小于 l_{i+1} 的，根据组合数计算方案，比较这个数量与 k 决定系数是 1 还是 w_i。f 同理，系数一定是 w_i。

转移到不确定的数的时候就好想一点了，分类讨论四种情况，f\rightarrow f 和 g\rightarrow g 的是好还得判断一下系数。

这样写出来是 O(Tn^4) 的，可以获得 65 分，只有分讨和加乘原理，考虑前缀和优化，把上面的东西写为主动转移，之后根据上一个 DP 数组的前缀和直接转移即可通过。

时间复杂度 O(Tn^3)，跑了 3.1s+eps 比较惊险。

代码不复原了，需要的找我要赛后拍的代码。