鱼C论坛

 找回密码
 立即注册
查看: 1183|回复: 15

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

[复制链接]
发表于 2022-9-13 20:19:03 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

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

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

还有,这个定理和动态规划有关系吗?

[哎,我这个蒟蒻什么都不会]
最佳答案
2022-9-14 18:24:00
zhangjinxuan 发表于 2022-9-13 21:16
不懂啊,能举个例子吗?

把序列分成不上升子序列的最少个数,等于序列的最长上升子序列长度
就是一个序列 , 你求它最少能有几个不上升子序列
然后这个最少的个数就是这个序列最长上升子序列长度
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2022-9-13 20:50:42 | 显示全部楼层
去看下这一题 : https://www.luogu.com.cn/problem/P1020
该定理在该问题上可以理解成:把序列分成不上升子序列的最少个数,等于序列的最长上升子序列长度。把序列分成不降子序列的最少个数,等于序列的最长下降子序列长度。

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

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

评分

参与人数 1荣誉 +1 鱼币 +1 收起 理由
zhangjinxuan + 1 + 1 有点似懂非懂,能具体一点吗?

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2022-9-13 21:16:29 | 显示全部楼层
柿子饼同学 发表于 2022-9-13 20:50
去看下这一题 : https://www.luogu.com.cn/problem/P1020

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

不懂啊,能举个例子吗?
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2022-9-13 21:37:05 | 显示全部楼层
本帖最后由 zhangjinxuan 于 2022-9-14 18:25 编辑

.
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2022-9-13 21:39:25 | 显示全部楼层
碎觉了,明天在搞吧
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2022-9-14 18:24:00 | 显示全部楼层    本楼为最佳答案   
zhangjinxuan 发表于 2022-9-13 21:16
不懂啊,能举个例子吗?

把序列分成不上升子序列的最少个数,等于序列的最长上升子序列长度
就是一个序列 , 你求它最少能有几个不上升子序列
然后这个最少的个数就是这个序列最长上升子序列长度
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2022-9-14 18:26:15 | 显示全部楼层
柿子饼同学 发表于 2022-9-14 18:24
把序列分成不上升子序列的最少个数,等于序列的最长上升子序列长度
就是一个序列 , 你求它最少能有几个 ...

大佬NB!
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2022-9-14 18:31:01 | 显示全部楼层

你真的懂了?
我不理解 , 之前发的帖里就有啊
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2022-9-14 18:38:18 | 显示全部楼层
柿子饼同学 发表于 2022-9-14 18:31
你真的懂了?
我不理解 , 之前发的帖里就有啊

大意是明白了,定理定理,背下来,记下来,应该就可以了吧
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2022-9-14 18:38:53 | 显示全部楼层
柿子饼同学 发表于 2022-9-14 18:31
你真的懂了?
我不理解 , 之前发的帖里就有啊

之前的帖子里有讲Dilworth吗
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2022-9-14 18:44:36 | 显示全部楼层
zhangjinxuan 发表于 2022-9-14 18:38
之前的帖子里有讲Dilworth吗

话说 , 这定理也就这种题里有用吧
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2022-9-14 18:46:07 | 显示全部楼层
本帖最后由 zhangjinxuan 于 2022-9-14 18:49 编辑
柿子饼同学 发表于 2022-9-14 18:44
话说 , 这定理也就这种题里有用吧


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

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

对于我这种蒟蒻,记住这个简单的是不是就可以了
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2022-9-14 18:51:15 | 显示全部楼层
zhangjinxuan 发表于 2022-9-14 18:46
对啊,我看有些地方,涉及到图了

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

好吧好吧 , 我也普及组呢
初赛加油啊
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2022-9-14 18:53:42 | 显示全部楼层
柿子饼同学 发表于 2022-9-14 18:51
好吧好吧 , 我也普及组呢
初赛加油啊


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

大佬那个省的啊?分数线高吗?
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2022-9-14 18:54:20 | 显示全部楼层
zhangjinxuan 发表于 2022-9-14 18:53
加油加油,祝你初赛100,复赛400

你也是 , 加油
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2023-8-23 21:11:59 | 显示全部楼层
学习
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-28 19:59

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表