Slope Trick 优化 DP

cforrest · 2025-04-07 06:59:57 · 题解

设 f(i,v) 为处理完前 i 堆泥土且结余 v 单位泥土的最小成本。问题的答案就是 f(n,0)。

可以写出状态转移方程：

其中，

是用于补足第 i 堆泥土的亏空（或盈余）（即 (b_i-a_i)-(w-v)）的成本，而 |w|Z 是将前一次剩余（或缺少）的土方搬到当前位置的新增成本。

方程只涉及分段线性的凸函数，因此考虑使用 slope trick。

在 f(i-1,w) 的基础上：

• 加 |w|Z 相当于在原点左侧的斜率都减去 Z，在原点右侧的斜率都加上 Z；
• 不考虑 (b_i-a_i) 项，后面就是 h(v-w)，将它与 f(i-1,w)+|w|Z 的和取 w 的最小值，相当于做 Minkowski 和，结果就是将 f(i-1,w)+|w|Z 的所有斜率（即差分）与 -Y 取最大值，与 X 取最小值；
• 最后，在得到的函数的基础上再加上 b_i-a_i 项相当于将它向左平移 b_i-a_i 的单位。

基于这些分析，只需要维护原点左右两侧离原点最近的几个斜率的值即可，事实上只需要两个栈。整体的操作用懒标记，左右移动只需要将栈顶的元素移动一下。

因为更远处的斜率一定为 -Y 或 X，所以不必记录，当左侧或右侧的栈空了的时候直接补相应的值即可。

最后的答案是 0 处的取值，所以在左右移动时需要更新答案。

复杂度是 O(n\max\{a,b\}) 的。

核心代码如下：

int main() {
    int n;
    long long x, y, z;
    std::cin >> n >> x >> y >> z;
    std::stack<long long> neg, pos;
    long long lt = 0, rt = 0;
    long long res = 0;
    for (; n; --n) {
        int a, b;
        std::cin >> a >> b;
        lt -= z;
        rt += z;
        for (; b < a; ++b) {
            auto l = -y;
            if (!neg.empty()) {
                l = std::max(l, neg.top() + lt);
                neg.pop();
            }
            pos.emplace(l - rt);
            res -= l;
        }
        for (; b > a; --b) {
            auto r = x;
            if (!pos.empty()) {
                r = std::min(r, pos.top() + rt);
                pos.pop();
            }
            neg.emplace(r - lt);
            res += r;
        }
    }
    std::cout << res;
    return 0;
}