作者shiauyeu (呵呵呵呵呵呵呵呵)
看板C_and_CPP
标题[问题] 最大平面弦集合的问题
时间Sun Nov 28 21:08:07 2021
https://imgur.com/a/YqHcSkJ
最近在解一个DP的问题
如上图这题的最大平面弦集合个数是3 分别是0 4、5 7、8 11
因为我用DP写出来的在喂5000条下跑得有够慢
所以我换了一种写法
我先把输入的弦两端相减求长度
比方说0 4相减是4，1 9相减是8 然後把所有长度做排序
排序完後以这题来说会是
5 7
8 11
0 4
2 6
3 10
1 9
接着把5 7包着的弦(6这条)删掉
8 11包着的弦(9和10两条)删掉
依此类推
最後出来的结果会是5 7、8 11、0 4
但是在喂500条执行出来的结果是错的 想上来问问大家 我想不出来这个方法为什麽不行
谢谢!!
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 114.45.73.44 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/C_and_CPP/M.1638104889.A.D91.html
1F：推 wtchen: 程式码呢？ 11/28 21:16
2F：推 gogogofuxk: 看内文像是从短做到长？反例：(0,10),(8,13),(12,30) 11/28 22:55
3F：→ gogogofuxk: btw 这感觉应该是interval scheduling的变形 11/28 22:56
4F：推 lc85301: 听你的描述，你是用了那个吧 11/29 10:47
5F：推 simon860730: 看来楼上跟我理解差不多 他应该是用了那个没错 11/29 11:23
6F：嘘 a28503662: 你应该跟我同班吧 作业自己写== 11/29 16:36
7F：推 a28503662: 翻了一下是学弟 而且还发过心得文 帮你补推== 11/29 16:41
8F：→ shiauyeu: 那个是哪个XD 後来我想了一下如同二楼举的反例 确实有BU 11/30 01:20
9F：→ shiauyeu: G 还是乖乖用DP 但是我写的DP光500条就要跑10秒左右XD 11/30 01:20
10F：推 f953024: 老实说你最大的问题就是用了那个吧 11/30 02:40
11F：推 lc85301: 这位先生叫武雄是吧 11/30 22:43
12F：推 ChineseKing: 你有没有想过你到底真正在追求什麽呢? 12/19 13:48
13F：推 alan23273850: 先问什麽叫做最大平面弦集合 12/28 19:11