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條執行出來的結果是錯的 想上來問問大家 我想不出來這個方法為什麼不行
謝謝!!

程式碼呢？

看內文像是從短做到長？反例：(0,10),(8,13),(12,30)btw 這感覺應該是interval scheduling的變形

聽你的描述，你是用了那個吧

看來樓上跟我理解差不多 他應該是用了那個沒錯

你應該跟我同班吧 作業自己寫==翻了一下是學弟 而且還發過心得文 幫你補推==

那個是哪個XD 後來我想了一下如同二樓舉的反例 確實有BUG 還是乖乖用DP 但是我寫的DP光500條就要跑10秒左右XD

老實說你最大的問題就是用了那個吧

這位先生叫武雄是吧

你有沒有想過你到底真正在追求什麼呢?

先問什麼叫做最大平面弦集合