问题描述 :
现在我有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 解出来的数字，这边就不知道怎么证了..