[問題] 最大平面弦集合的問題
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
推
11/28 21:16,
2年前
, 1F
11/28 21:16, 1F
推
11/28 22:55,
2年前
, 2F
11/28 22:55, 2F
→
11/28 22:56,
2年前
, 3F
11/28 22:56, 3F
推
11/29 10:47,
2年前
, 4F
11/29 10:47, 4F
推
11/29 11:23,
2年前
, 5F
11/29 11:23, 5F
噓
11/29 16:36,
2年前
, 6F
11/29 16:36, 6F
推
11/29 16:41,
2年前
, 7F
11/29 16:41, 7F
→
11/30 01:20,
2年前
, 8F
11/30 01:20, 8F
→
11/30 01:20,
2年前
, 9F
11/30 01:20, 9F
推
11/30 02:40,
2年前
, 10F
11/30 02:40, 10F
推
11/30 22:43,
2年前
, 11F
11/30 22:43, 11F
C_and_CPP 近期熱門文章
PTT數位生活區 即時熱門文章
