当前位置：首页 > news >正文

【详解】斜率优化 DP + 凸包

news 2024/11/18 9:40:14

凸包和凸包的维护

凸包的概念

先来了解凸包的概念。

凸包是一个类似于下面这样的东西。

顾名思义，它是凸的（一定是最凸的）。

这是一个下凸包，当然也有上凸包。

它是有多个点连成的边组成的。

凸包的维护

对于一个下凸包，我们可以发现它的每条边的斜率是递增的，于是我们可以用单调队列来维护一个凸包。

比如说，我们现在要将第 $i$ 个点加入这个凸包，我们只需要判断第 $q[tail-1]$ 个点和第 $q[tail]$ 个点连成的线的斜率和 $i$ 与 $q[tail]$ 形成的边的斜率的大小关系。

如果新加入的点 $i$ 与 $q[tail]$ 连成的线段的斜率比原来的要小（如上图所示），那说明它可以与 $q[tail-1]$ 形成更优的凸包，所以 tail--，以此往复。

如果新加入的点 $i$ 与 $q[tail]$ 连成的线段的斜率比原来的要大（如上图所示），那说明它可以加入到这个凸包之中，直接将 $i$ 入队。

同理，上凸包也一样，可以自己推推……

维护凸包局部代码：

#include<bits/stdc++.h>
using namespace std;
int x[100001],y[100001];//x[i]为第i个点的x坐标，y为第i个点的y坐标 
double slope(int i,int j)//计算斜率 
{return (y[j]-y[i])/(x[j]-x[i]);
}
int q[100001],n;
int main()
{int head=0,tail=1;for(int i=1;i<=n;i++){while(head<tail&&slope(q[tail],i)<=slope(q[tail-1],q[tail]))//head<tail，至少要两个点才能算斜率 tail--;q[++tail]=i;}
}

斜率优化 DP

ok, 讲完了凸包，接下来来讲斜率优化。

先以一个例题来讲吧……

例题：HDU 3507 Print Article

传送门https://acm.hdu.edu.cn/showproblem.php?pid=3507vjudge 传送门https://vjudge.net/problem/HDU-3507题目大意：

解题思路

设 $f(i)$ 表示打印前 $i$ 个文章的最小成本。

易得：

$f(i)=\min (f(j)+(s_i-s_j)^2+m)$

其中 $j<i$ ， $s_i$ 为 $c_i$ 的前缀和。

显然这样的转移是 $O(n^2)$ 的，那是包会超时的好吧！

优化

所以，我们得考虑优化……

先拆解这个转移方程，先不管 $\min$ 。

$f(i)=f(j)+(s_i-s_j)^2+m$

将平方项拆开，得：

$f(i)=f(j)+s_i^2+s_j^2-2s_is_j+m$

将 $j$ 看为未知数， $i$ 看为常数，把只含 $j$ 的项移到等号左边，得：

$-f(j)-s_j^2=-2s_is_j-f(i)+s_i^2+m$

两边同时乘 -1，得：

$f(j)+s_j^2=2s_is_j+f(i)+s_i^2+m$

这时，你觉得它像啥？

对，没错，就是 $y=kx+b$

我们将转移方程与 $y=kx+b$ 对比，可以得到：

$y=f(j)+s_j^2$

$k=2s_i$

$x=s_j$

$b=f(i)+s_i^2+m$

于是，对于每一个 $i$ ，我们可以把它抽象成二维平面上的点，每个点的坐标是 $(s_i,f(i)+s_i^2)$ 。

那是不是对于每一个 $i$ ，我们都可以找前面的一个点 $j$ 转移。

然后对于每一个点 $j$ ,都是不是会有一条 $f(j)+s_j^2=2s_is_j+f(i)+s_i^2+m (y=kx+b)$ 的直线经过它？

然后对于每一个点 $j$ ，都会有一条过它的斜率为 $2s_i$ 的直线，都会有一个截距 $f(i)+s_i^2+m$ 。

所以，就是要找一个点 $j$ ，使得过这个点的斜率为 $2s_i$ 的直线的截距最小，这样我们的 $f(i)$ 也就会最小了。

那你想想，这个点满足什么特性？

没错，它就是在下凸包上！

可是下凸包上有很多个点，该选哪个呢？

你觉得是 ①，②还是③？

由图像，我们可以发现①的截距是最小的？

那什么时候是最小的呢？

就是这个凸包上的点相邻的两条边的斜率刚好一条小于绿色线的斜率，一条大于绿色线的斜率。

所以，你可以二分查找凸包上的点。

当然，这题并没有必要，因为你可以发现 $2s_i$ 是单调递增的，也就是 $i$ 越大， $i$ 对应的斜率就越大。

也就是越往后，我们只会用到上一个 $i$ 用的之后的点。

所以可以一边入队，一边出队。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long 
int n,m;
int sum[500011];
int f[500011];
int q[500011];
int dx(int i,int j){return sum[i]-sum[j];
}
int dy(int i,int j)
{int y1=f[i]+sum[i]*sum[i];int y2=f[j]+sum[j]*sum[j];return y1-y2;
}
signed main()
{// ios::sync_with_stdio(false);// cin.tie(0);// cout.tie(0);while(scanf("%lld%lld",&n,&m)!=EOF){sum[0]=0;f[0]=0;for(int i=1;i<=n;i++){scanf("%lld",&sum[i]);sum[i]+=sum[i-1];}memset(q,0,sizeof q);memset(f,0,sizeof f);int head=1,tail=0;for(int i=1;i<=n;i++){while(head<tail&&dy(i-1,q[tail])*dx(q[tail],q[tail-1])<=dx(i-1,q[tail])*dy(q[tail],q[tail-1]))tail--;q[++tail]=i-1;while(head<tail&&dy(q[head+1],q[head])<=dx(q[head+1],q[head])*2*sum[i])head++;f[i]=f[q[head]]+(sum[i]-sum[q[head]])*(sum[i]-sum[q[head]])+m;}printf("%lld\n",f[n]);}return 0;
}