作者flere (人間失格)
站內Prob_Solve
標題[問題] 最少數量LIS覆蓋
時間Fri Aug 30 23:35:21 2013
問題描述 :
現在我有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
1F：推 singlovesong:LIS不是nlog(l) 的解法嗎 怎麼會TLE 08/31 01:24
2F：→ singlovesong:nlog(L) Q_Q 08/31 01:25
3F：→ pcyu16:先針對長或寬做 sorting, 再用另一個維度做 LIS 08/31 09:55
沒錯,這樣Nlog(N)的LIS還是會TLE!!!Q__Q
※ 編輯: flere 來自: 123.195.195.32 (08/31 09:58)
4F：→ pcyu16:那你應該是哪裡寫錯了吧..||| 這樣會TLE測資也太多... 08/31 09:59
他是要做"很多次" LIS把所有盒子合併起來耶
最慘的case就是全部都並不起來,
這樣的話就會TLE了
因為這樣就變成N * Nlog(N)
因為每做一次LIS就是要看N這麼多個
如果每次LIS都只有長度是1
那下次做的時候是N-1個
最後就變成至少N^2
還是我理解錯了嗎???
※ 編輯: flere 來自: 123.195.195.32 (08/31 10:37)
5F：→ scwg:LIS 作一次就可以找出最多可以串多少個箱子啦. 兩兩都無法放 08/31 10:38
6F：→ scwg:入的情況作一次就知道最長長度為一, 就輸出 n-1 啦 08/31 10:38
我覺得我題目可能沒說得很清楚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)
7F：推 pigalan:LDS 08/31 11:17
8F：→ scwg:題目是這樣的話根本不用做 LIS, 照第一維排序 (相等時照第二 08/31 11:26
9F：→ scwg:維排) 然後 greedy 掃一次, 也是 nlog n 應該就可以了 08/31 11:26
對耶!!!!感謝!!!!!!
這樣做完後就過了> <
雖然我掃了不只一次> <
※ 編輯: flere 來自: 123.195.195.32 (08/31 12:00)
10F：推 suhorng:pigalan的LDS是正解, O(n log n) 08/31 21:58
11F：→ suhorng:LDS就是把LIS的increasing改成decreasing 08/31 21:59
12F：→ suhorng:不過是跟 Dilworth's theorem 有關嗎orz 不太有印象 08/31 22:11
14F：→ suhorng:上面這個稍微不太一樣XD 08/31 22:11
15F：→ suhorng:等等XDDDD 先當我沒說 08/31 22:14
16F：推 scwg:沒錯, greedy 的時候做的確實是 longest decreasing sequence 09/01 00:15
17F：推 cutekid:有辦法證明 LDS 求出來的數字就等於最小盒子數嗎 09/09 17:40
18F：→ cutekid:最小盒子數不可能小於 LDS 求出來的數字，比較好理解 09/09 17:42
19F：→ cutekid:啊最小盒子數不可能大於 LDS 解出來的數字，這邊就不知道 09/09 17:43
20F：→ cutekid:怎麼證了.. 09/09 17:43
21F：推 ke1vin:dilworth 沒錯啊就是 dilworth 02/16 03:28