作者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/m.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