[問題] 最少數量LIS覆蓋

[flere (人間失格)]

問題描述 :

現在我有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


先感謝大家了!!> <



--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 123.195.195.32
推 singlovesong:LIS不是nlog(l) 的解法嗎 怎麼會TLE
→ singlovesong:nlog(L) Q_Q
→ pcyu16:先針對長或寬做 sorting, 再用另一個維度做 LIS
沒錯,這樣Nlog(N)的LIS還是會TLE!!!Q__Q
※ 編輯: flere           來自: 123.195.195.32       (08/31 09:58)
→ pcyu16:那你應該是哪裡寫錯了吧..||| 這樣會TLE測資也太多...
他是要做"很多次" LIS把所有盒子合併起來耶
最慘的case就是全部都並不起來,
這樣的話就會TLE了
因為這樣就變成N * Nlog(N)

因為每做一次LIS就是要看N這麼多個
如果每次LIS都只有長度是1
那下次做的時候是N-1個

最後就變成至少N^2
還是我理解錯了嗎???
※ 編輯: flere           來自: 123.195.195.32       (08/31 10:37)
→ scwg:LIS 作一次就可以找出最多可以串多少個箱子啦. 兩兩都無法放
→ scwg:入的情況作一次就知道最長長度為一, 就輸出 n-1 啦
我覺得我題目可能沒說得很清楚Q__Q
題目並不是要找LIS的長度,
而是要問幾個LIS可以把這個set給全部包含

比如說
5個物品
分別是 (10,10) (20,30) (39,51) (40,25) (41,26)
這樣做第一次LIS時可以拿到(10,10) (20,30) (39,51)
於是這3個盒子可以縮成一個盒子
總盒子剩下(40,25) (41,26)這二個 (還有一個剛剛已經縮成一個的盒子)

於是第二次LIS可以拿到 (40,25) (41,26)
於是這兩個縮成一個盒子

所以最後要輸出剩下2個盒子
並不是做完LIS後,輸出N-LIS的長度> <

※ 編輯: flere           來自: 123.195.195.32       (08/31 10:52)
※ 編輯: flere           來自: 123.195.195.32       (08/31 10:52)
推 pigalan:LDS
→ scwg:題目是這樣的話根本不用做 LIS, 照第一維排序 (相等時照第二
→ scwg:維排) 然後 greedy 掃一次, 也是 nlog n 應該就可以了
對耶!!!!感謝!!!!!!
這樣做完後就過了> <

雖然我掃了不只一次> <
※ 編輯: flere           來自: 123.195.195.32       (08/31 12:00)
推 suhorng:pigalan的LDS是正解, O(n log n)
→ suhorng:LDS就是把LIS的increasing改成decreasing
→ suhorng:不過是跟 Dilworth's theorem 有關嗎orz 不太有印象
→ suhorng:http://math.stackexchange.com/questions/438985
→ suhorng:上面這個稍微不太一樣XD
→ suhorng:等等XDDDD 先當我沒說
推 scwg:沒錯, greedy 的時候做的確實是 longest decreasing sequence
推 cutekid:有辦法證明 LDS 求出來的數字就等於最小盒子數嗎
→ cutekid:最小盒子數不可能小於 LDS 求出來的數字，比較好理解
→ cutekid:啊最小盒子數不可能大於 LDS 解出來的數字，這邊就不知道
→ cutekid:怎麼證了..
推 ke1vin:dilworth 沒錯啊就是 dilworth