网站首页
编程语言
数据库
系统相关
其他分享
编程问答
Xtot
2024-09-22
P5975 photo 题解
Solution先离散化,记\(f(l,r,p)\)为覆盖了\([l,r]\)区间内纵坐标\(\gep\)的点最少矩形个数。则:\[f(l,r,p)=\min(f(l,r,p),f(l,mid,p)+f(mid+1,r,p))\]\[f(l,r,p)=\min(f(l,r,p),f(l,r,res)+1)\]令\(h\)为用面积为\(S\)的矩形去覆盖\([l,r]\)区间的高度,即\(S/(r