栈中的数实际上对应一棵树。
加入相当于在当前节点挂一个儿子并将当前节点设置为新加入的儿子,删除相当于将当前节点退至父亲节点,< 相当于某个节点上方满足递增关系。
<
对于没有限制的点可以随便选取。对于有限制的点,我们可以树形 dp,设 fxf_xfx 表示 xxx 的子树内选取的方案数,简单转移即可。
时间复杂度 O(n)O(n)O(n)。
注册一个 CZOJ 通用账户,您就可以在我们提供的所有在线评测服务上提交代码、参与讨论。
使用您的 CZOJ 通用账户