省选-动态规划-Slope Trick · Zhl2010 第二博客

Slope Trick 是二维 dp 的优化方法，用于优化一个凹/凸函数。

我们利用分段点集合来表示这个函数。比如一个凹函数， ${-2,2,2}$ 表示在 $-2$ 的时候函数斜率 $-1$ ，在 $2$ 的时候 $-2$ ，然后还知道最后 $k=2,b=-6$ 。

$2024$ 年做这道题的时候，并不知道什么 Slope Trick，只是觉得这是一个技巧，可以水过好几倍经验。

$f_{i,j}$ 表示处理到 $i$ ，把它改成 $j$ 的最小操作次数。

f_{i,j} = \min_{k \le j} f_{i-1,k} + |a_i-j|

$f_i(x)$ 是一个凹函数。因为 $i=1$ 显然， $i>1$ 时，两个函数相加仍然是。

我们每一次输入 $a_i$ 都会让 $a_i$ 的斜率增加 $2$ 。然后每一次都需要 pop 来保证维护的是斜率最小的点，每一次的贡献就是最小值的点和当前的差的绝对值。

代码

C++

for (int i = 1; i <= n; i++)
    {
        int x; cin >> x;
        q.push(x); q.push(x);
        ans += q.top() - x;
        q.pop();
    }

设 $g_{i,j}$ 表示在 $i$ 这个点，所有儿子节点需要 $j$ 秒引爆的代价。这是一个凹函数。

然后我们还需要一个 $f_{i,j}$ 表示 $i$ 这个子树所有节点在 $j$ 秒引爆的代价。

设 $g_x$ 的最优区间为 $[L,R]$ 。

f_i(x)= \begin{cases} g_x + w & x\le L&\text{需要把这条边距离缩短为 0}\\ g_L + l-(x-L) & L<x\le L+l&\text{L 时间引爆需要修改的路径长度}\\ g_L&L+l<x\le R+l &\text{存在刚好能走完后恰到 x 的出发时间}\\ g_L + x-R-l&R+l<x&需要延长的路径长度 \end{cases}

其实后面的我也不知道怎么去想到，或许我们只是想优化一下转移。

接下来就用 Slope Trick 来维护了，用一个大根堆来维护。

再加上这个函数是连续的这个性质...

最后的答案就直接在根节点的堆里面，用 $f_0$ 减去所有拐点坐标就行了。