读完题以后，如果你觉得这和笛卡尔树，AVL 树有关，这题就基本结束了。
30pts
暴力枚举所有的方案，验证一下即可。
60pts
考虑转换题意，其实，每一名员工，左/右两个方向，上一步从哪来是确定的，这就是一棵笛卡尔树。
然后又要求两边的深度差不能超过 1，实际上这就是问：满足要求的笛卡尔树，且是 AVL 树的方案数是多少。
我们用 表示 个节点，最大深度是 的满足条件的树的方案数。
那么
这个 是的。
80pts
打完 60 分之后，可以输出一下 数组，会发现，其实 AVL 树真的是一棵平衡树，它的深度最大到 ，所以枚举的深度到 就得到了 80 分。
100pts
进一步思考，对于每一个深度 ，哪些范围的 才有解。
打个表可以发现，深度下界是一个递推序列，满足，上界 是。
那么，我们在转移时枚举的实际上限制多多，既要让 满足 的要求，又要让 满足 的要求，转移实际上是非常少的。
可以把这些取值区间拿出来求个交集，然后再去转移，就非常快。
STD选了一个可以通过，但是非常偷懒的做法，每次直接把从 枚举到 ，也是可以通过的。
关于复杂度的证明，可以按层来分析：
对于每一个 ，取值的区间长度在 级别，转移也在 级别，那么总复杂度：
。
如果只有 60~80 分做法，其实打表也是完全 OK 的，dp 数组可以复用，直接一次性花个几十秒把所有答案跑出来就行。