热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

LGP3240口胡

该死的破题意题意:给出一车不等式,问有多少种不同的可能的包含\(n-1\)个\(

该死的破题意

题意:给出一车不等式,问有多少种不同的可能的包含 \(n-1\) 个 \(<,=\) 和长度为 \(n\) 的排列,将符号插入排列后不会与给定的不等式冲突。

定义两个包含不等号和排列的“序列”相同的条件为不等号和排列能够推出的不等式相同。

首先给出的不等式中等号屁用没有,用并查集缩在一起。

容易发现剩下的部分是一车有根树。先建立超级源点链接所有有根树的根方便统计。

设这棵树的深度为 \(k\) ,那么此题等价将这棵树划分成 \(k\) 个部分,每个部分非空,且父子不能在同一个部分中。

这个相当简单,设 \(dp[u][k]\) 表示节点 \(u\) 在第 \(k\) “层”,子树内合法的划分方案数。只需要枚举子树 \(k\) 的 \(\min\) 就可以了。

可以轻松做到 \(O(n^3)\),线段树合并优化可以做到 \(O(n\log n)\)。(也许只能 \(O(n^2)\)?)



推荐阅读
author-avatar
荣星树
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有