网站首页
编程语言
数据库
系统相关
其他分享
编程问答
abc134E
2024-07-13
abc134E - Sequence Decomposing
abc134E-SequenceDecomposing题意:给定一个序列,将其划分成若干个不相交的严格上升子序列,求划分的最小的子序列数量。题解:我们可以定义严格偏序关系,\(i\precj\)当\(i<j\)且\(a_i<a_j\),也就是我们要将整个序列划分成若干个链。根据Dilworth’stheorem,最小链覆盖数=最大