斜率优化

1.引入

[COCI 2017/2018 #6] Cover作为一道简单题，我们可以快速的得到这样的转移方程

$f_{i,0}=min( f_{i-1,0},f_{i-1,1} )+w_i$

$f_{i,0}=min( y_j\times x_i+f_{j,0}-w_j ),j\in [1,i)$

我们就容易写出一个$O(n^2)$的代码

for( int i=1;i<=m;i++ )
{
	w[i]=p[i].x*p[i].y;
	f[i][0]=min( f[i-1][0],f[i-1][1] )+w[i];
	for( int j=1;j<i;j++ ) f[i][1]=min( f[i][1],p[j].y*p[i].x+f[j][0]-w[j] );
}

可以发现这个式子的复杂度瓶颈在于计算$f_{i,1}$时的枚举，那我们能不能更快的找到这个最优决策点呢

---

2.含义

斜率优化顾名思义就是通过计算斜率的方式来优化我们的决策

具体操作就是将转移方程类化为函数的形式再通过函数的单调性来确定最优决策

---

---

3.转化方式

例如上式$f_{i,0}=min( y_j\times x_i+f_{j,0}-w_j ),j\in [1,i)$

简化一下就是$f_{i,0}=y_j\times x_i+f_{j,0}-w_j$

我们不妨将每一个决策方式看作一条线(函数)，那么上式类化成形似$y=kx+b$的形式得到

$y=f_{i,0}，k=y_j，x=x_i，b=f_{j,0}-w_j$

我们发现在我们的第二次$j\in [1,i)$循环中的不变量全部被放到了$x$上面，其它项就是仅和含$j$的变化量有关的式子

那么我们就可以通过单调性来删去一些决策了，如图

我们相当于想要在得到的这些绿色的函数中快速选取红色的最优部分

---

4.实现

我们发现我们寻找的这个最优决策其实就是一个凸包，所以我们有如下的写法

I.单调队列维护凸包

首先的就是类似与上面这题的$O(n)$实现，它们都基于一个前提：

$k$和$x$都满足单调性，这样首先我们的新加入决策肯定是加入在最后的且决策路径单调，可以直接$O(1)$访问到最优决策

这里不妨看[COCI 2017/2018 #6] Cover的写法

struct LINE
{
    ll k, b;


    inline ll get( const ll &x )const//计算当前点情况下的函数值
    { QAQ k*x+b; }

};

inline bool check( LINE l1,LINE l2,LINE l3 )//维护凸包用判断新线段是否更优
{ QAQ ( intt )( l3.b-l1.b )*( l1.k-l2.k ) <= 
      ( intt )( l2.b-l1.b )*( l1.k-l3.k ); }

deque< LINE > dq;
w[1]=1ll*p[1].x*p[1].y;
f[1][0]=w[1]; f[1][1]=inf;
dq.push_back( { p[1].y,f[1][0]-w[1] } );
for( int i=2;i<=m;i++ )
{
    w[i]=1ll*p[i].x*p[i].y;
    f[i][0]=min( f[i-1][0],f[i-1][1] )+w[i];
    while( dq.size() >= 2 && dq[0].get( p[i].x ) >= dq[1].get( p[i].x ) ) dq.pop_front();//因为决策点单调，所以我们我们可以将不会更优的状态直接删去
    f[i][1]=dq.front().get( p[i].x );//留下的最老状态就是我们的最优决策
    LINE nl={ p[i].y,f[i][0]-w[i] };//计算新的函数
    while( dq.size() >= 2 && check( dq[dq.size()-2],dq[dq.size()-1],nl ) ) dq.pop_back();//维护凸包
    dq.push_back( nl );
}

II.二分决策点

这种情况是因为我们的决策点也就是$x$不单调导致的，具体看图

从黑色到蓝色的决策就类似于I情况，我们不会访问前面的函数所以我们可以一点点删去最先前的不会更优的那些决策

但是像从黑色到绿色的决策就需要我们保留整个凸包而不能删去前面的点

但是我们又容易发现这个凸包与其对应构成的函数是单调的，所以我们可以再这个凸包上二分来寻找最优决策点

也就是所谓的二分队列，这里提供「一本通 5.6 例 3」任务安排 3的代码

inline int bound( int k )
{
	if( l == r ) QAQ q[l];
	int L=l, R=r;
	while( L < R )
	{
		int mid=L+R>>1;
		if( f[q[mid+1]]-f[q[mid]] <= k*( sumc[q[mid+1]]-sumc[q[mid]] ) ) L=mid+1;
		else                                                             R=mid;
	}
	QAQ q[L];
}

f[0]=0;
q[++r]=0;
for( int i=1;i<=n;i++ )
{
    int p=bound( s+sumt[i] );
    f[i]=f[p]-( s+sumt[i] )*sumc[p]+sumt[i]*sumc[i]+s*sumc[n];
    while( l < r && ( f[q[r]]-f[q[r-1]] )*( sumc[i]-sumc[q[r]] ) >= ( f[i]-f[q[r]] )*( sumc[q[r]]-sumc[q[r-1]] ) ) r--;
    q[++r]=i;
}

III.平衡树动态维护

如果说$k$或$x$都不单调(因为只有其中之一不单调我们可以转化式子)，那么我们就又会发现一个问题

如果说蓝色是我们要新添加的函数，那么我们维护凸包就不是在最后加而是再中间加

这种情况我们就不得不再使用一个平衡树来维护这种中间加入的情况了，但是正常情况考不到(考了我也不会)

---

5.时间复杂度

和上面所说的一样，复杂度就是维护凸包的$O(n)~O(nlogn)$加上选择决策点的$O(1)~O(logn)$

时间复杂度：$O(n)~O(nlog^2n)$

---

6.Trick

我们发现斜优的题目为什么一定是斜优是因为我们有一个$不变项\times 变化项+变化项$

否则我们可以直接单调队列维护了，但是双不变项其中还有一个变换项就导致我们的决策变成了一个个函数的形式

但是斜优还有一个大前提：函数单调性

因为我们是通过计算当前情况的值来维护凸包的，但是非单调性函数会导致现在选的点不会更优