正文

浅谈斜率优化

Philchieh  Philchieh  2022-10-05  339

关键词：

斜率优化

如果对于方程形如这样的

我们不能对其进行比较有效果的优化，因为它的转移，涉及到了关于i和关于j的一些数组，这时我们就需要用斜率优化了。

通常我们令k<j<i，且用j来更新F[i]比用j优。则有

并且我们都可以化成如下形式，X[j],Y[j]指只关于j的数，X[k],Y[k]亦之

我们可以根据这个式子，来优化DP。这大概就是斜率优化的主要思想

实践出真知，让我们看一下HDU3507吧

很容易可以推出状态转移方程

令k<j<i，那么就可以得到

移项可得

如果我们令Y[i]=F[i]+A[i]²,X[i]=A[i]，那么可以转化成如上形式

优化DP

根据刚才的推算，可以发现，要是满足这个条件的转移，选j一定比k要优。

我们抽象的把X[i],Y[i]想象成平面上的点，那么这个式子所表示的含义就是两个点所连成的这条线的斜率。

但是这个斜率又是怎么样的呢？

我们令g(i,j)表示i点和j点的斜率（上面式子的左边，k<j<i）。假设g(i,j)<g(j,k)。①如果g(i,j)<F[i]（这个F[i]斜率式子右边的F[i]）那么i一定比j优，则j不必选。②如果g(i,j)>F[i]，那么j比i优，但是k又比j优，还是不选j。

总结出来，如果g(i,j)<g(j,k)，那么j就是废物，可以T掉。

我们发现，这种情况就是

那么最后剩下的图形，就是一个下凸包壳，也就是斜率单调

优化实现

我们就例题而言

维护一个单调队列p.get为斜率

表示存的可能为答案的点。因为我们要维护下凸包的性质，必须满足get(p[tail-1],p[tail])>get(p[tail],i)

我们根据斜率式子，队首必须满足get(p[head],p[head+1])<2A[i]

因为斜率越小越优，所以每次选队首。

大致可以有如下代码：

while (head<tail) and (get(p[tail-1],p[tail])>get(p[tail],i)) do dec(tail);

加入新增可供转移的节点

while (head<tail) and (get(p[head],p[head+1])<...) do inc(HeaD)

动态规划转移

练习题

bzoj1010[HNOI2008]玩具装箱

bzoj1096[ZJOI2007]仓库建设

bzoj1597[USACP2008 Mar]土地购买

bzoj1911[Apio2010]特别行动队

bzoj3156 防御准备

bzoj3675[Apio2014] 序列分割

bzoj3437 小P的牧场

bzoj4518[SDOI2016] 征途

uvalive4726average——（斜率优化dp）

...这是第一次写斜率优化DP==。具体的做法参照周源论文《浅谈数形结合思想在信息学竞赛中的应用》。这里仅提供一下AC的代码。　　有两点值得注意：1.我这个队列的front和back都是闭区间的；2.在while(...)front++;这个循环里面，<=... 查看详情

斜率优化规律

斜率单调暴力移指针斜率不单调二分找答案x坐标单调开单调队列x坐标不单调开平衡树|cdq分治——摘自MashiroSky ——ta讲解的斜率优化查看详情

dp斜率优化

斜率优化入门题：PKU3709很多人貌似都是做这道题来K斜率优化的，所以看了资料以后还是开始入手吧。然而还是得跪求大神的程序啊ORZORZ…… 其实理解斜率优化就是会列斜率不等式，还要理解剔除过程。那么我们来看... 查看详情

斜率优化小结

斜率优化小结博主是个智障，总是忘记斜率优化的过程。为了方便以后考前临时抱佛脚，写个博客。斜率优化维护下面的问题：(f_i=min_j<if_j+(a_i-b_j)^2)其中(min)或(max)，和(+)或(-)。(a_i,b_j)均只取决于(i,j)。首先不看取(min)。我们钦... 查看详情

斜率优化dp

斜率优化DP是一种DP的一种优化方式，目的在于将一类具有单调性的DP优化为线性。注：本文只适用于较为基础的斜率优化DP，以便为初学者提供一个思路。这一类可以利用单调性线性或(log)复杂度之内求解的DP问题统称为1D/1D类型... 查看详情

斜率优化

斜率优化说明(本文中所有的单调递增递减都不是绝对的，根据实际情况灵活使用)对于形如$f[i]=max$$f[j]+a[i]+b[i]*c[j]$的状态转移方程，若$b[i]$是单调递增的(可以是递减，但维护方式就不同了，下面不再说明)，那么我们可以对... 查看详情

斜率凸优化小结

斜率凸优化小结前言很久以前考了一道叫做"林克卡特树"的题目(还记得被八省联考支配的恐惧吗？)正解是用直线去切一个凸函数......当时并不是很会。然而$APIO$讲课竟然讲了并且卧槽我竟然还听懂了。所以就回来把这... 查看详情

bzoj2720浅谈期望线性性分部转移

读《代码整洁之道》合并两个有序的链表Spring+SpringMVC+hibernate整合开发BZOJ4518征途[nlogn做法][斜率优化]g0a蒲辗诒http://p.baidu.com/ihome/center?uid=c3fa61626362363763663028a9&29uy=k8涡睬盎68ffkl性钠酚http://p.baidu.com/ihome/center?uid 查看详情

斜率优化复习小结

这篇基本上还是自己看的，写一些碎片和注意事项斜率优化：①形如DP[i]=min/max{DP[j]+A[j]+B[j]*C[i]+D[i]+E}方程，将转移方程化为(DP[j]+A[j])=(-C[i])*(B[j])+(DP[i]-D[i]-E)　　即方程斜率式:y=kx+b,其中k=-C[i]　　要求C[i]单调！(斜率单调)　　... 查看详情

斜率优化dp

hihocoder1529不上升序列[斜率优化]Description给出一个序列(a[1...n])，求构造一个(b[1...n])，满足(b_i+1leb_i)，使得(sumlimits_i=1^n|a_i-b_i|)最小.(nle5 imes10^5)Solution关于暴力与转移方程首先对于暴力转移，定义(dp_i,j)为转移到i点，权查看详情

斜率优化动态规划学习笔记

发掘状态转移方程的性质发掘状态转移方程的性质本文作者：ztxcsl，使用署名-非商业性使用4.0国际进行许可查看详情

斜率优化dp

前置知识　　比记号与拓展比记号: http://www.cnblogs.com/Sdchr/p/7347799.html [HDU3507]PrintArticle 　　以[HDU3507]来说明清楚斜率优化. 　　序列$s_1,s_2,...,s_n$满足$s_1les_2le...les_n$.　　$f_0=0$.　　$f_i=min_{0le 查看详情

斜率优化dp和四边形不等式优化dp整理

...一重循环跑i的所有子状态）这样的时间复杂度是O(N^2)而斜率优化或者四边形不等式优化后的DP可以将时间复杂度缩减到O(N)O(N^2)可以优化到O(N),O(N^3)可以优化到O(N^2),依次类推斜率优化DP和四边形不等式优化DP主要的原理就是利用斜... 查看详情

uva1451average-斜率优化

　　ADNAsequenceconsistsoffourletters,A,C,G,andT.TheGC-ratioofaDNAsequenceisthenumberofCsandGsofthesequencedividedbythelengthofthesequence.GC-ratioisimportantingenefindingbecauseDNAsequenceswithrelative 查看详情

『这是一篇干货blog』

...过来。各文章版权归原作者所有，仅做搬运工作，侵删。浅谈C++IO优化——读优输优方法集锦浅谈斜率优化思维导图好助手——开心食用XmindTypora---一款简洁的Markdown编辑器在线生成树图csacademy在线平面直角坐标系和函数解析desmos... 查看详情

斜率优化(代码片段)

对于有i*j的项，考虑用斜率优化DP（任务安排）http://poj.org/problem?id=1180 单调递增1memset(f,8,sizeof(f));f[0]=0;2FOR(i,1,n)34while(l<r&&(f[q[l+1]]-f[q[l]])<=(sumc[q[l+1]]-sumc[q[l]])*(sumt[i]+s))++l;5f[i 查看详情

4518:[sdoi2016]征途|斜率优化

裸的斜率优化。。我考场上SB写暴力#include<algorithm>#include<iostream>#include<complex>#include<cstdlib>#include<cstring>#include<cstdio>#include<vector>#include<cmath> 查看详情

hdu3507单调队列斜率优化

斜率优化的模板题给出n个数以及M，你可以将这些数划分成几个区间，每个区间的值是里面数的和的平方+M，问所有区间值总和最小是多少。如果不考虑平方，那么我们显然可以使用队列维护单调性，优化DP的线性方法来做，但是... 查看详情