zhangjinxuan 发表于 2022-9-13 20:19:03

请问Dilworth定理是什么，请大佬解答

本帖最后由 zhangjinxuan 于 2022-9-13 20:30 编辑

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

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

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

柿子饼同学 发表于 2022-9-13 20:50:42

去看下这一题 : https://www.luogu.com.cn/problem/P1020
该定理在该问题上可以理解成：把序列分成不上升子序列的最少个数，等于序列的最长上升子序列长度。把序列分成不降子序列的最少个数，等于序列的最长下降子序列长度。

则第二问等价于最长上升子序列。
第二问就是它的应用 , 去看看题解

zhangjinxuan 发表于 2022-9-13 21:16:29

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

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

不懂啊，能举个例子吗？

zhangjinxuan 发表于 2022-9-13 21:37:05

本帖最后由 zhangjinxuan 于 2022-9-14 18:25 编辑

.

zhangjinxuan 发表于 2022-9-13 21:39:25

碎觉了，明天在搞吧

柿子饼同学 发表于 2022-9-14 18:24:00

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

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

zhangjinxuan 发表于 2022-9-14 18:26:15

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

大佬NB！

柿子饼同学 发表于 2022-9-14 18:31:01

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

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

zhangjinxuan 发表于 2022-9-14 18:38:18

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

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

zhangjinxuan 发表于 2022-9-14 18:38:53

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

之前的帖子里有讲Dilworth吗

柿子饼同学 发表于 2022-9-14 18:44:36

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

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

zhangjinxuan 发表于 2022-9-14 18:46:07

本帖最后由 zhangjinxuan 于 2022-9-14 18:49 编辑

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

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

但问题不大，CSP-J不会考{:5_109:}

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

柿子饼同学 发表于 2022-9-14 18:51:15

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

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


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

zhangjinxuan 发表于 2022-9-14 18:53:42

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

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

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

柿子饼同学 发表于 2022-9-14 18:54:20

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

你也是 , 加油

unsigned_int 发表于 2023-8-23 21:11:59

学习
页: [1]
查看完整版本: 请问Dilworth定理是什么，请大佬解答