P7690 [CEOI2002] A decorative fence 做题记录

求字典序第 $k$ 小的对任意一个 $2\le i\le n-1$ 的 $i$ 满足 $p_{i-1}>p_i<p_{i-1}$ 或 $p_{i-1}<p_i>p_{i+1}$ 的 $n$ 的排列 $p$。$1\le n\le 20,1\le k\le \text{满足条件的排列数量}$

考虑是先上后下还是先下后上，设 $dp_{n,i}$ 为先上后下，长度为 $n$，$p_1=i$ 的方案数；$pd_{n,i}$ 为先下后上，长度为 $n$，$p_1=i$ 的方案数。

那么有转移：

$dp_{n,i}=\sum\limits_{j=i}^{n-1}pd_{n-1,j}$

$pd_{n,i}=\sum\limits_{j=1}^{i-1}dp_{n-1,j}$

即考虑在前面插入数 $i$。

考虑构造答案，显然若 $p_1$ 相同，那么先下后上是更优的。

那么从前往后考虑构造答案即可，不过构造时要注意编号的变换。

记得开 long long。