高度由习惯堆积

分类 算法:区间dp 下的文章

July 21, 2019

BZOJ1766 Photo

PDF题目平面上有若干个点,现在要求用最少的底边在X轴上且面积小等A的矩形覆盖所有点,这些矩形可以重叠。 N<=100,A<=2000000思路一开始想的是简单的区间dp。$f[l,r]$表示覆盖完$[l,r]$一段区间的所有点的最小矩形数,然后很快就发现了不对之处:对于图中所示情况,单纯考虑区间之间的分割是行不通的,也就是说,对于相互重叠的矩形,高度那一维也很有必要记录。重新定...
February 17, 2019

HDU 6049 Sdjpx Is Happy

题目Sdjpx is a powful man,he controls a big country.There are n soldiers numbered 1~n(1<=n<=3000).But there is a big problem for him.He wants soldiers sorted in increasing order.He find a way t...