P9084 [PA 2018] Skwarki 笔记

题目的意思是，如果一个数是局部最大值（单峰），就不删除它。

所以一个数被删除的原因是遇上了左边或右边一个更大的值，这启示将排列描述为笛卡尔树。

对笛卡尔树进行 DP，设 $f_{i,j,0/1}$ 表示考虑长度为 $i$ 的子序列，需要删除 $j$ 次的方案数，$0/1$ 表示这一段子序列是不是序列的边界状态（因为边界只能被一边删去），初始时，$f_{0,0,\ast }\leftarrow 1$。

考虑枚举其最大值出现的位置 $c$，拆分成左子树和右子树，则有 $f_{i,j,0}\leftarrow f_{c-1,p,0}\times f_{i-c,q,0}\times (\genfrac{}{}{0ex}{}{i-1}{c-1})$，分析可得 $j\leftarrow max(p,q)+[p=q]$，因为若左右子树同时删完，根节点多删一次。

对于边界，$f_{i,max(p,q+1),1}\leftarrow f_{c-1,p,1}\times f_{i-c,q,0}\times (\genfrac{}{}{0ex}{}{i-1}{c-1})$，首先选定一边子树为边界，若右子树删完了，左子树还没删完，根节点会在第 $p$ 次删除被一并删去，否则需要单独删掉根节点。

最终统计答案时，同理枚举最大值出现的位置 $i$，得到 $f_{i-1,p,1}$ 和 $f_{n-i,q,1}$，若 $max(p,q)=k$，则为合法方案。

状态数 $O(n\log n)$，转移 $O(n\log n)$，时间复杂度 $O(n^2{\log }^{2}n)$。