PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

[問題] 最少數量LIS覆蓋

看板Prob_Solve (計算數學 Problem Solving)作者flere (人間失格)時間11年前 (2013/08/30 23:35)推噓6(6推 0噓 15→)

留言21則, 7人參與討論串1/1

問題描述 : 現在我有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

08/31 01:24, , 1^F

08/31 01:24, 1^F

→

singlovesong

08/31 01:25, , 2^F

08/31 01:25, 2^F

→

pcyu16

08/31 09:55, , 3^F

08/31 09:55, 3^F

沒錯,這樣Nlog(N)的LIS還是會TLE!!!Q__Q ※ 編輯: flere 來自: 123.195.195.32 (08/31 09:58)

→

pcyu16

08/31 09:59, , 4^F

08/31 09:59, 4^F

他是要做"很多次" LIS把所有盒子合併起來耶最慘的case就是全部都並不起來, 這樣的話就會TLE了因為這樣就變成N * Nlog(N) 因為每做一次LIS就是要看N這麼多個如果每次LIS都只有長度是1 那下次做的時候是N-1個最後就變成至少N^2 還是我理解錯了嗎??? ※ 編輯: flere 來自: 123.195.195.32 (08/31 10:37)

→

scwg

08/31 10:38, , 5^F

08/31 10:38, 5^F

→

scwg

08/31 10:38, , 6^F

08/31 10:38, 6^F

我覺得我題目可能沒說得很清楚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

08/31 11:17, , 7^F

08/31 11:17, 7^F

→

scwg

08/31 11:26, , 8^F

08/31 11:26, 8^F

→

scwg

08/31 11:26, , 9^F

08/31 11:26, 9^F