网站首页
编程语言
数据库
系统相关
其他分享
编程问答
P2900
2024-08-28
P2900 [USACO08MAR] Land Acquisition G
题目思路我们按照土地的长为第一关键字,土地的宽为第二关键字,从大到小排序,对于将被大矩形完全包含的小矩形删去,因其不影响结果,这样就得到了长严格下降,宽严格上升的序列。从左往右考虑合并,假如将\(l\)到\(r\)段合并,那么长取矩形\(l\)的长\(w_l\),宽取矩形\(r\)的宽\(h_
2024-07-29
P2900 [USACO08MAR] Land Acquisition G
P2900[USACO08MAR]LandAcquisitionG传送门思路:先将土地按照长\(H\)排序从后往前遍历如果有出现\(H[i]\leH[j]\\text{and}\W[i]\leW[j]\)则这块土地是没有贡献的(\(i\)与\(j\)拼单)处理完之后H从小到大有序,W从大到小有序方程:\(f[i]=f[j-1]+max(h[k])*