警告

本 Blog 仅供蒟蒻 tiger0132 复习用。本蒟蒻

不对其内容正确性做任何保证。

若发现 Bug 请在评论区反馈。本蒟蒻欢迎一切形式的贡献。

点击屏幕以关闭。

「洛谷 P2900」土地征用 - 斜率优化 + DP

题意

传送门:洛谷 P2900 - 土地征用

给你一堆二元组 \((a_i, b_i)\),你可以把它们分成一堆集合。每个集合的代价是 \(\max_{a \in S} \times \max_{b\in S}\)。求最小代价。

解法

注意到如果对于两个二元组 \((a, b), (x, y)\)\(a \le x\)\(b \le y\),那么 \((a, b)\) 就不会对答案产生贡献。

考虑对二元组排序。\(a_i\) 为第一关键字,\(b_i\) 为第二关键字。对于每一个相同的 \(a_i\),用单调栈 / 双指针去除无用的二元组。

可以证明,排序并去除无用二元组后,最优选法的每个集合下标都是连续的。

那么这题又变成了一道序列分段的题,显然又是 DP。那么我们可以得到下列方程:

\[\displaystyle dp_i = \max_{0 \le j < i} \left\{ dp_j + a_ib_{j+1} \right\}\]

注意到这个方程符合 \(dp_i = \max \{ dp_j + w(i, j) \}\) 的形式,且 \(w(i, j)\) 包含 \(i\)\(j\) 的乘积项。考虑斜率优化。

假设我们在计算 \(dp_i\),且有两个决策 \(x, y\) 满足 \(\mathbf{x > y}\)\(\mathbf{x}\) 优于 \(\mathbf{y}\)。即 \[ \begin{align*} dp_x + a_ib_{x+1} & < dp_y + a_ib_{y+1} \\ dp_x - dp_y & < a_i(b_{y+1} - b_{x+1}) \\ \frac {dp_x - dp_y} {b_{y+1} - b_{x+1}} & < a_i \end{align*} \]\(\operatorname{slope}(x, y) = \frac {dp_x - dp_y} {b_{y+1} - b_{x+1}}\)。我们维护一个单调队列,使得从队尾到队首,\(\operatorname{slope}(x+1, x)\) 递增,保证队首决策最优。每次决策从队首转移。因为每个元素入队出队次数都是 \(O(1)\) 的,且转移复杂度也是 \(O(1)\),所以总复杂度为 \(O(n)\)

代码