2019 ICPC Asia Xuzhou Regional K K-rectangle【ICPC徐州J】【DP】【斜率优化】【可回退化凸包】
题目大意 平面上有 nnn 个点，求用若干个底落在xxx轴的矩形来覆盖所有点，并且使得代价最小. 其中一个w⋅hw\cdot hw⋅h矩形的代价为(w+k)⋅h(w+k)\cdot h(w+k)⋅h，kkk为大于000的常数。 n≤4⋅105，k≤106n\le 4\cdot 10^5，k\le 10^6n≤4⋅105，k≤106题解 这种题最容易想到的就是dpdpdp，dp[i]...
