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]...