斜率优化dp

关键词：

hihocoder 1529 不上升序列

[斜率优化]

Description

给出一个序列 (a[1...n]) ，求构造一个 (b[1...n]) ，满足(b_i+1le b_i)，使得 (sumlimits _i=1^n |a_i-b_i|) 最小 .

• (nle 5 imes 10^5)

Solution

关于暴力与转移方程

首先对于暴力转移，定义(dp_i,j)为转移到i点，权值为j的最小花费.

那么有转移方程 $dp_i+1,j= min(dp_i,k)+|A_i-j| $ [k>=j]

函数图像及证明

然后分析(dp_i,j) 构成的函数，定义 (f(x)=dp_i) ，那么可以得到(f(x))是一个下凸函数 [斜率单调不递减]

首先对于i=1的情况，图像是：

很显然是一个下凸函数

其中y表示花费，x表示b1的取值，a1表示原来第一个点的值

再观察上面给出的转移方程，发现对于一个j，用到的是大于等于自己的k对应的最小值

所以那段下降的函数是无用的

如果要转移到下一层的话，我们就只用管：

然后加入a2，但考虑a2构成的图像是和上面a1的图像相同的，然后再与修改后的转移图像相叠加，不难发现图像的斜率单调不减

所要维护的东西

由上面的推导可知：

加入一个数之后，图像会有所改变，并且我们不用管斜率小于等于0的部分函数

所以就始终维护一个斜率大于0且单调递增函数即可，并且答案就为那个下凹点

假设我们考虑 (a_i) ，那么 (x< a_i)的部分的斜率都要 -1，(x> a_i)的部分斜率都要 +1

如何维护斜率

加入第一个点后 (f(x)) 是一个斜率为1的递增函数

那么就放入(a_1)，表示 ([a_1,infty]) 的局部函数斜率都为1

如果加入一个 (a_2)

若(a_2ge a_1) ，那么 ([a_1,a_2]) 的局部函数斜率变为0 ，([a_2,infty]) 斜率变为2

若(a_2<a1) ，那么 ([a_2,a_1]) 的局部函数斜率变成1，([a_1,infty]) 的斜率变为2

对于第一种情况，可以看做 ([a1,infty]) $ o $ ([a1,a2],[a2,a2],[a2,infty]) 分别对应 0,1,2三种斜率

对于第二种情况，可以看做 ([a1,infty]) $ o $ ([a2,a1],[a1,infty]) 分别对应 1,2两种斜率

已知斜率小于等于0的函数部分是不要的

所以对于第一种情况，应该把(a_1)这个点给删掉，并加入两个(a_2)

而第二种情况，只需加入(a_2)即可

发现每次只需要调用最左边的点[即最小值]，所以用堆维护即可

如何计算答案

发现对于上述第一种情况，整个函数的下凹点改变了，假设原来凹点为(f(a_1)=y_1) ,(，f(a_2)=y_1+k imes (a_2-a_1)，k=1) ，那么斜率改变后， 凹点位置转移到(a_2)，对应 (f(a_2))不变，所以答案增大(a_2-a_1)

RT

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

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

[dp优化方法之斜率dp]

什么是斜率dp呢大概就把一些单调的分组问题从O(N^2)降到O(N)具体的话我就不多说了看论文:http://www.cnblogs.com/ka200812/archive/2012/08/03/2621345.html 我自己也补充几句：其实斜率dp有很多种打法有凸包有截距有直接比较斜率的因为我比... 查看详情

斜率优化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点，权 查看详情

斜率优化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

转载自http://www.cnblogs.com/ka200812/archive/2012/08/03/2621345.html我们知道，有些DP方程可以转化成DP[i]=f[j]+x[i]的形式，其中f[j]中保存了只与j相关的量。这样的DP方程我们可以用单调队列进行优化，从而使得O(n^2)的复杂度降到O(n)。 可... 查看详情

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

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

斜率优化dp学习

转自：http://www.cnblogs.com/ka200812/archive/2012/08/03/2621345.html我们知道，有些DP方程可以转化成DP[i]=f[j]+x[i]的形式，其中f[j]中保存了只与j相关的量。这样的DP方程我们可以用单调队列进行优化，从而使得O(n^2)的复杂度降到O(n)。 可... 查看详情

hdu2829之二维斜率优化dp

T.E.LawrencewasacontroversialfigureduringWorldWarI.HewasaBritishofficerwhoservedintheArabiantheaterandledagroupofArabnationalsinguerillastrikesagainsttheOttomanEmpire.Hisprimarytargetsweretherailroads 查看详情

hdu2829lawrence(斜率优化dp或四边形不等式优化dp)

...，肯定会超时，就要对其进行优化。有两种方式，一种是斜率对其进行优化，是一个很简单的斜率优化dp[i][j]= min{dp[i- 查看详情

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

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

hdu3507斜率优化dp

PrintArticleTimeLimit:9000/3000MS(Java/Others)    MemoryLimit:131072/65536K(Java/Others)TotalSubmission(s):11141    AcceptedSubmission(s):3393ProblemDescription 查看详情

hdu4258斜率优化dp

CoveredWalkwayTimeLimit:30000/10000MS(Java/Others)    MemoryLimit:131072/131072K(Java/Others)TotalSubmission(s):1496    AcceptedSubmission(s):602ProblemDescript 查看详情

hdu3507斜率优化dp

PrintArticleTimeLimit:9000/3000MS(Java/Others)    MemoryLimit:131072/65536K(Java/Others)TotalSubmission(s):12185    AcceptedSubmission(s):3733ProblemDescription 查看详情

斜率优化第一题！hdu3507|单调队列优化dp

放一手原题 题解：第一次写（抄）斜率优化，心里还是有点小激动的。讲一下怎么实现的！首先我们可以考虑一个朴素的dp：DP[i]表示前i个数字的最少花费，显然我们有一个转移方程DP[i]=min{DP[j]+M+(sum[i]-sum[j])^2}但是N^2肯定会... 查看详情

hdu3507：printarticle（斜率优化dp）(代码片段)

...与\(i,j\)两个变量有关，这种一般可以考虑分离变量然后斜率dp优化。(P 查看详情

hdu3507printarticle（斜率dp优化）(代码片段)

ProblemDescriptionZerohasanoldprinterthatdoesn‘tworkwellsometimes.Asitisantique,hestillliketouseittoprintarticles.Butitistoooldtoworkforalongtimeanditwillcertainlywearandtear,soZerouseacosttoevaluatet 查看详情

[bzoj3156]防御准备斜率优化dp

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=3156裸的斜率优化，记一下以后复习用吧。要直接dp很明显应该要倒着dp，很不爽，先把它倒过来。令$sum[j]=sum_{i=1}^ji$，于是我们首先推出这样一个方程$$f[i]=min{f[j]+sum[i-1]-sum[j]-(i-j-1)*... 查看详情

斜率优化复习小结

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