链接:hdu3669
题解
- 把给的矩形以长为第一关键词宽为第二关键词降序排列,去掉包含的矩形,定义dp[j][i]表示前i个矩形挖了j个洞的最小花费
- 维护一个上凸曲线即可.(注意细节,并且如果挖洞数增加了花费没有变小那么break,不然会T)
1 |
|
learn
链接:hdu3669
- 把给的矩形以长为第一关键词宽为第二关键词降序排列,去掉包含的矩形,定义dp[j][i]表示前i个矩形挖了j个洞的最小花费
- 维护一个上凸曲线即可.(注意细节,并且如果挖洞数增加了花费没有变小那么break,不然会T)
1 | #include<iostream> |