关键词：

斜率优化

说明(本文中所有的单调递增递减都不是绝对的，根据实际情况灵活使用)

对于形如\(f[i]=max\)\(f[j]+a[i]+b[i]*c[j]\)的状态转移方程，若\(b[i]\)是单调递增的(可以是递减，但维护方式就不同了，下面不再说明)，那么我们可以对决策进行斜率优化。

证明

显然，对于两个决策\(j和k(j<k)\),决策\(k\)要优于决策\(j\)当且仅当
\[f[j]+a[i]+b[i]*c[j]\leq f[k]+a[i]+b[i]*c[k]\]
移项后
\[b[i]*(c[j]-c[k]) \leq f[k]-f[j]\]
除过去
\[-b[i] \leq \fracf[k]-f[j]c[k]-c[j]\]

所以若\(-b[i] \leq \fracf[k]-f[j]c[k]-c[j]\),那么本次决策中决策\(k\)优于决策\(j\)
(之后所说的斜率均为\(\fracf[k]-f[j]c[k]-c[j]\))(\(k>j\))

维护

删除

对于这个我们可以用一个单调队列来维护一个单调递减的斜率。
因为\(b[i]\)是单调递增的，所以若决策\(k\)在一次决策中要优于决策\(j\)，那么之后的所有决策中决策\(k\)都是要优于决策\(j\)的，这时我们就可以把决策\(j\)丢出单调队列

插入

插入一个决策时，由于我们要让斜率满足单调递减，所以若之前的斜率要小于现在的斜率，那么当前面那个斜率被删除后，这个斜率也一定会被删除，也就是说之前队尾的就决策没有用了，直接删除就好(若不删除，可能出现三个决策\(a,b,c,决策a优于决策\)b\(但决策c优于决策a,但是由于决策b的阻隔，妨碍了决策c的使用\))。

这样一来，我们每次只需选择队首的决策即可。
然后每个决策最多被插入和删除一次，所以时间复杂度是线性的，一般都能将\(O(n^2)的转移优化成O(n)\)

斜率优化的方法大概就是这样，还是需要灵活运用。

斜率优化小结

斜率优化小结博主是个智障，总是忘记斜率优化的过程。为了方便以后考前临时抱佛脚，写个博客。斜率优化维护下面的问题：(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类型... 查看详情

浅谈斜率优化

斜率优化如果对于方程形如这样的我们不能对其进行比较有效果的优化，因为它的转移，涉及到了关于i和关于j的一些数组，这时我们就需要用斜率优化了。通常我们令k<j<i，且用j来更新F[i]比用j优。则有并且我们都可以化... 查看详情

斜率优化

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

斜率凸优化小结

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

斜率优化复习小结

这篇基本上还是自己看的，写一些碎片和注意事项 斜率优化：①形如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 查看详情

斜率优化(代码片段)

对于有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的线性方法来做，但是... 查看详情

动态规划专题——斜率优化dp

前言斜率优化(DP)是难倒我很久的一个算法，我花了很长时间都难以理解。后来，经过无数次的研究加以对一些例题的理解，总算啃下了这根硬骨头。基本式子斜率优化(DP)的式子略有些复杂，大致可以表示成这样：[f_i=min_j=1^i-1(A(... 查看详情

『土地征用landacquisition斜率优化dp』(代码片段)

斜率优化DP的综合运用，对斜率优化的新理解。详细介绍见『玩具装箱TOY斜率优化DP』土地征用LandAcquisition(USACO08MAR)DescriptionFarmerJohnisconsideringbuyingmorelandforthefarmandhashiseyeonN(1<=N<=50,000)additionalrectangularplots,eachwithintegerdimensions(1&l... 查看详情

「斜率优化」解析及例题

...此不能再用单调队列直接来进行优化了，这时候就要用到斜率优 查看详情

玩具装箱bzoj1010斜率优化

斜率优化的题好像都是这样的方程：左边关于j，k的一个(...)/(...)的式子，右边是个只与i有关的可算的数字；然后把它放到二维坐标轴上，用单调队列维护一个凸壳，O（n）的复杂度；这道题但是我发现我wrong了，找了程序看了一... 查看详情