连续段插入型 DP

【P5999】求排列 $p$ 的数量，满足 $p_i$ 两边的数同时小于或大于 $p_i$，且 $p_1=S$, $p_N=T$。

$f(n,m)$：前 $n$ 小的值分成 $m$ 段的方案数。

从小到大加入每一个数，考虑现在枚举到 $n$，若 $n \neq S$ 且 $n\neq T$，则可以分三种情况讨论：

1. 新开一段
   • 若 $n \neq S$ 且 $n\neq T$，以后 $n$ 两侧的都比它大，与题意相符，转移 $f(n,m) \gets (m-[n>S]-[n>T]) f(n-1,m-1)$。
   • 若 $n = S$ 或 $n = T$，与题意相符，转移 $f(n,m) \gets f(n-1,m-1)$。
2. 接在某一段头 / 尾
   • 若 $n \neq S$ 且 $n\neq T$，以后一定有一个 $>n$ 的数接在 $n$ 另一侧，$n$ 两侧就有一个大于的和一个小于的，与题意不符。
   • 若 $n = S$ 或 $n = T$，与题意相符，转移 $f(n,m) \gets f(n-1,m)$。
3. 将两段连起来
   • 若 $n \neq S$ 且 $n\neq T$，此时 $n$ 两侧的都比它小，与题意相符，转移 $f(n,m) \gets m f(n-1,m+1)$。
   • 若 $n = S$ 或 $n = T$，与题意不符。

答案为 $f(N,1)$。