对于二分斜率优化DP几种不同的理解方法

将DP的一维通过二分斜率优化为一个的做法在当今OI界已广泛运用了

本文是我初步学习二分斜率优化DP的理解。

设DP答案关于二分斜率的那一维的函数为

不严格单调是二分斜率的条件。我们再考虑二分斜率的过程。

 

为了方便表述,假设这一维要求为

 

组合意义上

我们二分一个值。给这一维上的所有贡献减去

然后通过不考虑这一维,我们可以求出最优解并同时记录下它在这一维上的坐标。

然后,我们通过得到的坐标来二分调整的值,最后得到坐标为时的答案。

这样正确的原因是因为单调,所以每次这一维上多增加一个增加的贡献是单调不增的。

所以增加一个恰当的时,可以使得前次贡献大于等于而后面的贡献都

所以可以使答案恰好选个作为贡献。

 

代数意义上

我们要求的就是的值。

我们可以看看函数,不难发现它是凸函数或凹函数。

由于是单调的,那么不同位置的切线斜率不同,那么我们可以通过确定斜率来确定位置从而求出值。

现在我们二分这个斜率,由于是切线,我们要发现线经过这个点时,比经过其他所有点时的截距都大或小。

我们假设这个截距是最小的。

那么这个截距等于,由于它是最小的。

我们DP的时候对于每一次贡献都加上过后,求出的最小值就是加上的值。

同时维护坐标,那么我们可以得到切线为该斜率时的横坐标。

 

对于斜率相同的一些连续的点

我们可以找到所属的区间,然后我们直接用最左的值和斜率算出答案。