dp trick 之「连续段插入 dp」

模拟赛 T2 遇到的。对这类问题，一般会按值大小插入以消除后效性，先只在每段内考虑限制，再在两个段合并时考虑限制。P5999题意转化为求有多少个 $1 \sim n$ 的排列 $p$ 满足 $p_i$ 两边的数字同时大于或同时小于 $p_i$，且 $p_1 = s, p_n = t$。设 $f_{i, j}$ 表示前 $i$ 个数，分成 $j$ 段的方案数。从小到大加入每个数，对于 $i \...