不保证最优,若有更优解法请回复告知。
数位动规。
必须承认本题出得不好(我太菜了),因为「子树有序」这条件实在不优雅。
将 $n$ 节点、子树有序的有根树转化为长度为 $2(n-1)$ 的括号序列,问题便相当显豁了。
会了吧?
—
——
———
————
———
——
—
设状态 $s_{i,j}$ 代表括号序列的前 $i$ 位、左括号比右括号多 $j$ 个的情况数。当 $j\gt0$ 时,$s_{i,j}$ 可以转移到 $s_{i+1,j-1}$;当 $j\lt k-1$ 时,$s_{i,j}$ 可以转移到 $s_{i+1,j+1}$。
初始条件为 $s_{0,0}=1$,答案为 $s_{2(n-1),0}$,效率为 $\Theta(nk)$。
由于是大水题,代码非常好写,就不放标程了。
——故国神游,多情应笑我,早生华发。