Slope Trick 优化 DP

设

f(i,v)

为处理完前

i

堆泥土且结余

v

单位泥土的最小成本。问题的答案就是

f(n,0)

。

可以写出状态转移方程：

f(i,v) = \min_w f(i-1,w)+|w|Z+h((b_i-a_i)-(w-v)),

其中，

h(\delta) = \max\{\delta,0\}X+\max\{-\delta,0\}Y

是用于补足第

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\})

的。

核心代码如下：

CPP

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;
}

文章操作

相关推荐

评论

Slope Trick 优化 DP