[已解决]请问Dilworth定理是什么，请大佬解答

zhangjinxuan

之前刷题遇到过，便想网上搜搜，但是网上搜的许多都看不懂，请鱼C大佬详细解答解答

还有，这个定理和动态规划有关系吗？

[哎，我这个蒟蒻什么都不会]

最佳答案

月排行榜 / 总排行榜

柿子饼同学

2022-9-14 18:24:00

zhangjinxuan 发表于 2022-9-13 21:16
不懂啊，能举个例子吗？

把序列分成不上升子序列的最少个数，等于序列的最长上升子序列长度
就是一个序列 , 你求它最少能有几个不上升子序列
然后这个最少的个数就是这个序列最长上升子序列长度

跳转到最佳答案楼层

柿子饼同学

去看下这一题 : https://www.luogu.com.cn/problem/P1020

该定理在该问题上可以理解成：把序列分成不上升子序列的最少个数，等于序列的最长上升子序列长度。把序列分成不降子序列的最少个数，等于序列的最长下降子序列长度。

则第二问等价于最长上升子序列。

第二问就是它的应用 , 去看看题解

zhangjinxuan

柿子饼同学 发表于 2022-9-13 20:50
去看下这一题 : https://www.luogu.com.cn/problem/P1020

第二问就是它的应用 , 去看看题解

不懂啊，能举个例子吗？

zhangjinxuan

.

zhangjinxuan

碎觉了，明天在搞吧

柿子饼同学

zhangjinxuan 发表于 2022-9-13 21:16
不懂啊，能举个例子吗？

把序列分成不上升子序列的最少个数，等于序列的最长上升子序列长度
就是一个序列 , 你求它最少能有几个不上升子序列
然后这个最少的个数就是这个序列最长上升子序列长度

zhangjinxuan

柿子饼同学 发表于 2022-9-14 18:24
把序列分成不上升子序列的最少个数，等于序列的最长上升子序列长度
就是一个序列 , 你求它最少能有几个 ...

大佬NB！

柿子饼同学

zhangjinxuan 发表于 2022-9-14 18:26
大佬NB！

你真的懂了?
我不理解 , 之前发的帖里就有啊

zhangjinxuan

柿子饼同学 发表于 2022-9-14 18:31
你真的懂了?
我不理解 , 之前发的帖里就有啊

大意是明白了，定理定理，背下来，记下来，应该就可以了吧

zhangjinxuan

柿子饼同学 发表于 2022-9-14 18:31
你真的懂了?
我不理解 , 之前发的帖里就有啊

之前的帖子里有讲Dilworth吗

柿子饼同学

zhangjinxuan 发表于 2022-9-14 18:38
之前的帖子里有讲Dilworth吗

话说 , 这定理也就这种题里有用吧

zhangjinxuan

柿子饼同学 发表于 2022-9-14 18:44
话说 , 这定理也就这种题里有用吧

对啊，我看有些地方，涉及到图了

但问题不大，CSP-J不会考

对于我这种蒟蒻，记住这个简单的是不是就可以了

柿子饼同学

zhangjinxuan 发表于 2022-9-14 18:46
对啊，我看有些地方，涉及到图了

但问题不大，CSP-J不会考

好吧好吧 , 我也普及组呢
初赛加油啊

zhangjinxuan

柿子饼同学 发表于 2022-9-14 18:51
好吧好吧 , 我也普及组呢
初赛加油啊

加油加油，祝你初赛100，复赛400

大佬那个省的啊？分数线高吗？

柿子饼同学

zhangjinxuan 发表于 2022-9-14 18:53
加油加油，祝你初赛100，复赛400

你也是 , 加油

unsigned_int

学习