UOJ Logo NaCl的博客

博客

题解:#373. 赤壁怀古

2020-12-02 21:00:19 By NaCl
不保证最优,若有更优解法请回复告知。

数位动规。

必须承认本题出得不好(我太菜了),因为「子树有序」这条件实在不优雅。

将 $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)$。

由于是大水题,代码非常好写,就不放标程了。

——故国神游,多情应笑我,早生华发。

评论

No_wonder
%%
No_wonder
是用prufer编码做吗

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。