[問題] 最大平面弦集合的問題 shiauyeu PTT批踢踢實業坊

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

作者: shiauyeu (呵呵呵呵呵呵呵呵) 2021-11-28 21:08:07

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

作者: wtchen (沒有存在感的人) 2021-11-28 21:16:00

程式碼呢？

作者: gogogofuxk (小炫) 2021-11-28 22:55:00

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

作者: lc85301 (pomelocandy) 2021-11-29 10:47:00

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

作者: simon860730 (╰電磁學╮╭爆炸囉╯) 2021-11-29 11:23:00

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

作者: a28503662 (Ok Rocker) 2021-11-29 16:36:00

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

作者: shiauyeu (呵呵呵呵呵呵呵呵) 2021-11-30 01:20:00

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

作者: f953024 (=.=a) 2021-11-30 02:40:00

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

作者: lc85301 (pomelocandy) 2021-11-30 22:43:00

這位先生叫武雄是吧

作者: ChineseKing (安安) 2021-12-19 13:48:00

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

作者: alan23273850 2021-12-28 19:11:00

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

繼續閱讀

[問題][QT] windeploy 之後程式邏輯出錯liu2007 [問題] 後輸入運算式，堆疊後歸零justgetup [問題] LFU實作問題ars0921 Re: [問題] QT Sqlite語法以及全文檢索FTS問題pinefruit [問題] QT Sqlite語法以及全文檢索FTS問題liu2007 [問題] 新手請問opencv讀取Vvvahc Re: [問題] auto用法一問dzwei [問題] 矩陣相乘irpolo1 [問題] 請問ffmpeg如何build msvc不做optimize?Keitaro [問題] C語言初學觀念請益how0919