[問題] 最大平面弦集合的問題

[shiauyeu (呵呵呵呵呵呵呵呵)]

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://www.ptt.cc/bbs/C_and_CPP/M.1638104889.A.D91.html
推 wtchen: 程式碼呢？
推 gogogofuxk: 看內文像是從短做到長？反例：(0,10),(8,13),(12,30)
→ gogogofuxk: btw 這感覺應該是interval scheduling的變形
推 lc85301: 聽你的描述，你是用了那個吧
推 simon860730: 看來樓上跟我理解差不多 他應該是用了那個沒錯
噓 a28503662: 你應該跟我同班吧 作業自己寫==
推 a28503662: 翻了一下是學弟 而且還發過心得文 幫你補推==
→ shiauyeu: 那個是哪個XD 後來我想了一下如同二樓舉的反例 確實有BU
→ shiauyeu: G 還是乖乖用DP 但是我寫的DP光500條就要跑10秒左右XD
推 f953024: 老實說你最大的問題就是用了那個吧
推 lc85301: 這位先生叫武雄是吧
推 ChineseKing: 你有沒有想過你到底真正在追求什麼呢?
推 alan23273850: 先問什麼叫做最大平面弦集合