作者:荣星树 | 来源:互联网 | 2024-09-27 21:16
该死的破题意
题意:给出一车不等式,问有多少种不同的可能的包含 \(n-1\) 个 \(<,=\) 和长度为 \(n\) 的排列,将符号插入排列后不会与给定的不等式冲突。
定义两个包含不等号和排列的“序列”相同的条件为不等号和排列能够推出的不等式相同。
首先给出的不等式中等号屁用没有,用并查集缩在一起。
容易发现剩下的部分是一车有根树。先建立超级源点链接所有有根树的根方便统计。
设这棵树的深度为 \(k\) ,那么此题等价将这棵树划分成 \(k\) 个部分,每个部分非空,且父子不能在同一个部分中。
这个相当简单,设 \(dp[u][k]\) 表示节点 \(u\) 在第 \(k\) “层”,子树内合法的划分方案数。只需要枚举子树 \(k\) 的 \(\min\) 就可以了。
可以轻松做到 \(O(n^3)\),线段树合并优化可以做到 \(O(n\log n)\)。(也许只能 \(O(n^2)\)?)