P7690 [CEOI2002] A decorative fence 做题记录

求字典序第 kk 小的对任意一个 2in12\le i\le n-1ii 满足 pi1>pi<pi1p_{i-1}>p_i<p_{i-1}pi1<pi>pi+1p_{i-1}<p_i>p_{i+1}nn 的排列 pp1n20,1k满足条件的排列数量1\le n\le 20,1\le k\le \text{满足条件的排列数量}

考虑是先上后下还是先下后上,dpn,idp_{n,i} 为先上后下,长度为 nnp1=ip_1=i 的方案数;pdn,ipd_{n,i} 为先下后上,长度为 nnp1=ip_1=i 的方案数

那么有转移:

dpn,i=j=in1pdn1,jdp_{n,i}=\sum\limits_{j=i}^{n-1}pd_{n-1,j}

pdn,i=j=1i1dpn1,jpd_{n,i}=\sum\limits_{j=1}^{i-1}dp_{n-1,j}

即考虑在前面插入数 ii

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

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

记得开 long long