浅谈斜率优化dp -凯发ag旗舰厅登录网址下载

前言

考试 t2 出题人放了个树上斜率优化 dp，直接被同校 oier 吊起来锤。

离 noip 还有不到一周，赶紧学一点。

引入

斜率

斜率，数学、几何学名词，是表示一条直线（或曲线的切线）关于（横）坐标轴倾斜程度的量。它通常用直线（或曲线的切线）与（横）坐标轴夹角的正切，或两点的纵坐标之差与横坐标之差的比来表示。

斜率可以用来描述一个坡的倾斜程度，公式 \(k = \frac{\delta y}{\delta x}\)。

初中学过一元一次函数 \(y = kx b\)，这里的 \(k\) 就是这个函数表示的直线的斜率。

解决什么

一般对于形如 \(f[i] = \min(a[i] \times b[j] c[i] d[j])\) 这种类型的 dp 转移式子都可以用上斜率优化。

其中 \(b\) 要满足单调递增。

看到中间有一部分与 \(i,j\) 都有关，所以这个时候要用到斜率优化。

理解

下面来以一道题目为例进行讲解。

p3195 [hnoi2008] 玩具装箱

看完题目应该都可以想出来一个 \(o(n^2)\) 的 dp，那就是：

设 \(f[i]\) 表示考虑到第 \(i\) 个玩具所用的最小花费，\(sum[i]\) 为从 \(1\sim i\) 的玩具长度总和。

\[f[i] = \min\{f[j] (sum[i] - sum[j] i - j - l - 1)^2\} \]

我们尝试把这一堆东西分分类，把只有 \(i\) 的挪到一起，只有 \(j\) 的挪到一起，剩下的挪到中间。

得到：

\[f[i] = \min\{f[j] (sum[i] i - sum[j] - j - l - 1)^2\} \]

设 \(a=sum[i] i, b = sum[j] - j - l - 1\)。

那么就是 :

\[f[i] = f[j] a^2 -2ab b^2 \]

显然的，\(a^2\) 我们可以预处理，是已知的，由于前缀和，而且玩具长度至少为 \(1\)，所以 \(2a\) 是严格单调递增的，\(b\) 数组我们也可以直接预处理。

\[f[j] b^2 = 2ab f[j] a^2 \]

这个式子是把只与 \(j\) 有关的移到左边了，可以发现形式上是和 \(y = kx b\) 一样的。

那么我们就可以把一个之前转移完成的状态看成是一个 \((b, f[j] b^2)\) 的点，而 \(2a\) 就是经过他们的直线的斜率。

那么我们要求 \(f[i]\) 的话，就是求这个点和这个斜率为 \(2a\) 的直线的最大可能截距是多少。

于图像中

假设下面的三个点是我们待选的状态：

假设我们当前要求的斜率画出来是下面这样：

我们就从下往上，一点一点向上挪，直到碰到的第一个点，此时的截距一定最大。我们也能看出的确 \(c\) 点最优。

那么此时的 \(a\) 点好像没有什么用了，可以扔掉吗？

答案是可以，因为斜率是单调递增的，既然这次第一个碰不到 \(a\)，那么后面肯定也不是第一个碰到。

但是我们如何做到最快找出呢？

队列维护

观察这张图片，假设里面的点都是之前转移完的状态。

比较 \(ae,ab\) 的斜率。

不难发现 \(ab\) 的斜率比 \(ae\) 小，想一下之前说的，如果拿一条直线去碰这个图形，从各个角度去碰，最外层的点会形成一个凸包，而这个凸包内的点，是无论如何都碰不到的。

这个我们可以用一个队列来维护一个下凸壳，也就是凸包的一部分。

然后根据上面说的，要是队列头的两个元素形成的直线斜率比当前的小，也可以直接弹出。

这样队列的队头元素就是我们要转移的值了。

code：

/*
 * @author: aisaka_taiga
 * @date: 2023-11-13 14:11:27
 * @lastedittime: 2023-11-13 15:09:40
 * @lasteditors: aisaka_taiga
 * @filepath: \desktop\p3195.cpp
 * the heart is higher than the sky, and life is thinner than paper.
 */
#include 
#define pf(x) ((x) * (x))
#define int long long
#define db double
#define n 1000100
using namespace std;
inline int read()
{
    int x = 0, f = 1;
    char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') f = -1; c = getchar();}
    while(c <= '9' && c >= '0') x = (x << 1)   (x << 3)   (c ^ 48), c = getchar();
    return x * f;
}
int n, l, q[n], c[n], f[n], sum[n], a[n], b[n];
inline int x(int x){return b[x];}
inline int y(int x){return f[x]   pf(b[x]);}
inline db xl(int i, int j){return (y(i) - y(j)) * 1.0 / (x(i) - x(j));}
signed main()
{
    n = read(), l = read();
    for(int i = 1; i <= n; i   ) c[i] = read();
    for(int i = 1; i <= n; i   )
    {
        sum[i] = sum[i - 1]   c[i];
        b[i] = sum[i]   i   l   1;
        a[i] = sum[i]   i;
    }
    b[0] = l   1;
    int h = 1, t = 1;
    for(int i = 1; i <= n; i   )
    {
        while(h < t && xl(q[h], q[h   1]) < 2 * a[i]) h   ;
        int j = q[h];
        f[i] = f[j]   pf(a[i] - b[j]);
        while(h < t && xl(q[t - 1], i) < xl(q[t - 1], q[t])) t --;
        q[   t] = i;
    }
    cout << f[n] << endl;
    return 0;
}

参考：https://www.cnblogs.com/terribleterrible/p/9669614.html

总结

以上是凯发ag旗舰厅登录网址下载为你收集整理的浅谈斜率优化dp的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得凯发ag旗舰厅登录网址下载网站内容还不错，欢迎将凯发ag旗舰厅登录网址下载推荐给好友。