斜率优化讲解

内容预览:
  •   首先,斜率优化用于什么问题呢?当我们有一个dp题目的时候,发现如...~
  • 下面我给出一个式子: $f+calc(j)$~
  •   $f+i)$,$l=l+1$~

斜率优化讲解

  最近学习了一下斜率优化,在这里讲解一下我本人的理解。

  首先,斜率优化用于什么问题呢?当我们有一个dp题目的时候,发现如果正常写代码会TLE,这时候我们就可以想一想单调队列优化,或者是斜率优化,亦或是别的算法。下面我给出一个式子: $f[i]=f[j]+calc(j)$。

  我首先要讲解一下单调队列的适用范围,并且让大家回顾一下单调队列(斜率优化也需要单调队列进行维护)。我们看上面这个式子,是不是大多数的dp式子的模型?就是不同题目中calc这个函数的运算不同,如果当calc之中的每一项都只含有i或者是j,这两个字母,没有相乘的情况我们就可以用单调队列,这个不难理解,举个例子,像下面的这个式子:$f[i]=max$,就可以用单调队列维护,因为整个式子之中只有关于i的单独项和关于j的单独项。但是像这样的式子就不可以了:$f[i]=max$,因为这个式子展开后就会出现关于I的式子乘上关于j的式子。下面我要讲解一下斜率优化的应用。

  我们读一道题目,并以这道题目为例题:链接——bzoj1010玩具装箱toy。

  第一步(列方程):这道题目很容易就能够分析出来是一道dp的题目,dp方程是:f[i]表示打包到第一个玩具的最小费用,sum[i]表示的是一号玩具到第i号玩具的长度和,$f[i]=min$,这个方程是不是很好理解?

  第二部(数学部分,移项):对于这道题目,我们可以运用斜率优化,而斜率优化的最关键的步骤就是移项这一步。

  $f[i]=f[j]+(sum[i]-sum[j]+i-j-1-l)^2 Downarrow$

  $f[i]=f[j]+[(sum[i]+i)-(sum[j]+j)-(l+1)]^2 Downarrow$

  令$s[i]$表示$(sum[i]+i)$,$l=l+1$。

  $f[i]=f[j]+(s[i]-s[j]-l)^2 Downarrow$

  $f[i]=f[j]+s[i]^2+(s[j]+l)^2-2*s[i]*(s[j]+l) Downarrow$

  $f[i]+2*s[i]*(s[j]+l)=f[j]+s[i]^2+(s[j]+l)^2$

  就这样式子就变形好了,我们观察,这个式子是不是和直线的$y=kx+b$很像?我们可以设方程之中的$(s[i]+l)$为横坐标,$2*s[i]$为斜率k,$f[i]$为纵坐标上的截距,$f[j]+s[i]^2+(s[j]+l)^2$为纵坐标,这样我们就可以的每一个I的式子就可以有一个点(s[i]+i,f[i])(注:因为我们下面要求的是斜率,所以两个点的横坐标相减,纵坐标相减,相同的项会被减掉,所以就只剩下前面所书写的点的坐标之中的式子了),这样我们可以绘制一个图(下图),斜率优化就是在更新i的时候把之前所有的点放在图中,并用当前直线去切,找到结局最小的点,并更新。在下图之中,我们可以发现,这个点一定在我们维护的凸包上,像点B这样的点就不能被用来更新,下图之中只有点D在当前直线上时能使斜率最小,根据是由点D转移,我们可以发现,当两个点(A,C)的斜率小于2*s[i]的时候,横坐标小的点一定不能用来转移,同理斜率大于2*s[i]的两个点,横坐标大的也不能够用来转移,这个性质是不是很好?

  下面就是这道玩具装箱的代码,如果还有不会的,可以根据代码理解一下。

#include <stdio.h>

#define N 50001
int n,l,head,tail;
long long f[N],s[N],q[N];
double re_x(int i)
double re_y(int i)
double re_k(int i,int j)
int main()
{
scanf("%d%d",&n,&l);
for(int i=1;i<=n;i++)
scanf("%lld",&s[i]),s[i]+=s[i-1];
for(int i=1;i<=n;i++) s[i]+=i;
q[tail]=0;
for(int i=1;i<=n;i++)
{
while(head<tail&&re_k(q[head],q[head+1])<2*s[i]) head++;
f[i]=f[q[head]]+(s[i]-s[q[head]]-l-1)*(s[i]-s[q[head]]-l-1);
while(head<tail&&re_k(q[tail],i)<re_k(q[tail],q[tail-1])) tail--;
q[++tail]=i;
}
printf("%lldn",f[n]);
}

  如果还有不会的,可以发评论问我,或者是推荐两篇博客链接1(作者:大米饼),链接2(作者:同届神犇JZYshuraK)。

和大佬一起学习网络安全知识

以上就是:斜率优化讲解 的全部内容

本站部分内容来源于互联网和用户投稿,如有侵权请联系我们删除,谢谢^^
Email:[email protected]


0 条回复 A 作者 M 管理员
    所有的伟大,都源于一个勇敢的开始!
欢迎您,新朋友,感谢参与互动!欢迎您 {{author}},您在本站有{{commentsCount}}条评论