問題描述 :
現在我有M個盒子, (1<=M<=20000)
每個盒子有兩個資訊,長和寬 (w,h) (1<=w,h<=10000)
盒子不能旋轉
也就是長寬不能互換
盒子(w',h')可以放進另一個盒子(w,h)
只有當 w' < w 且 h' < h
的時候才可以放進去
問題是,最後能剩下多少盒子?? 求最小值
不知道這個要怎麼做比較好OAO?
直接排序做LIS的話會TLE> <
因為最糟的case可以設計成全部都無法合併
比如說
M = 2
(10,3)
(3,10)
之類的Q__Q
先感謝大家了!!> <

dilworth 沒錯啊就是 dilworth

LIS不是nlog(l) 的解法嗎 怎麼會TLEnlog(L) Q_Q

先針對長或寬做 sorting, 再用另一個維度做 LIS那你應該是哪裡寫錯了吧..||| 這樣會TLE測資也太多...

LIS 作一次就可以找出最多可以串多少個箱子啦. 兩兩都無法放入的情況作一次就知道最長長度為一, 就輸出 n-1 啦

LDS

題目是這樣的話根本不用做 LIS, 照第一維排序 (相等時照第二維排) 然後 greedy 掃一次, 也是 nlog n 應該就可以了

pigalan的LDS是正解, O(n log n)LDS就是把LIS的increasing改成decreasing不過是跟 Dilworth's theorem 有關嗎orz 不太有印象http://math.stackexchange.com/questions/438985上面這個稍微不太一樣XD等等XDDDD 先當我沒說

沒錯, greedy 的時候做的確實是 longest decreasing sequence

有辦法證明 LDS 求出來的數字就等於最小盒子數嗎最小盒子數不可能小於 LDS 求出來的數字，比較好理解啊最小盒子數不可能大於 LDS 解出來的數字，這邊就不知道怎麼證了..