求字典序第 k 小的对任意一个 2≤i≤n−1 的 i 满足 pi−1>pi<pi−1 或 pi−1<pi>pi+1 的 n 的排列 p。1≤n≤20,1≤k≤满足条件的排列数量
考虑是先上后下还是先下后上,设 dpn,i 为先上后下,长度为 n,p1=i 的方案数;pdn,i 为先下后上,长度为 n,p1=i 的方案数。
那么有转移:
dpn,i=j=i∑n−1pdn−1,j
pdn,i=j=1∑i−1dpn−1,j
即考虑在前面插入数 i。
考虑构造答案,显然若 p1 相同,那么先下后上是更优的。
那么从前往后考虑构造答案即可,不过构造时要注意编号的变换。
记得开 long long
。