作者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