斜率优化

例1 ：[HNOI2008]玩具装箱

定义状态：$f[i]$ 前 $i$ 个玩具打包压缩费用最低

$f[i]=min( f[j]+(sum[i]-sum[j]+i-(j+1)-L)^2),0 \le j \le i $ ,$sum(i)= {\textstyle \sum_{1}^{i}C_i}$

最小化函数，为了找到内在关系，暂时去掉 min，可以得到

$f[i]= f[j]+((sum[i]+i)-(sum[j]+j+L+1))^2$, 令 $a[i]=(sum[i]+i),b[j]=(sum[j]+j+L+1)$，可得

$f[i]=f[j]+a[i]^2+b[j]^2 - 2*a[i]*b[j]$，要使得$f[i]$ 最小，此时决策 $j$ 是变量，可以将状态转移方程变为 $f[j]+b[j]^2 = 2*a[i]*b[j] +f[i]-a[i]^2$

令 $y（j）=f[j]+b[j]^2,x(j)=b[j]$，原方程变为 $y = 2*a[i]*x +f[i]-a[i]^2$

对于确定的$i$ ，$2*a[i]$ 为定值且大于零，方程表示斜率为 $2*a[i]$ ，截距为 $f[i]-a[i]^2$ 的一条直线，截距越小,$f[i]$ 越小。

取任意三个决策点 $(x(j_1),y(j_1)),(x(j_2),y(j_2)),(x(j_3),y(j_3))$ ,设 $j_1<j_2<j_3$ ，前缀和 $x[j]=b[j]=(sum[j]+j+L+1)$ 递增，有 $x(j_1)<x(j_2)<x(j_3)$ 。

“及时排除无用决策”，通过绘图，当这三个点构成上凸时，决策点 $j_2$ 永远不会被选中，也就是我们要维护一个相邻点斜率递增的候选集合,也就是斜率单调递增的“下凸壳”。

斜率 $2*a[i]$ 会随着 $i$ 增大变大，那么队首两点斜率如果小于 $2*a[i]$ 队首点也出队，队首点不会是最优点，循环出队直到队首两点斜率大于 $2*a[i]$ ，队首点才是最优点，进行状态转移。

新的决策点进入队列，队尾两点间斜率如果大于队首与新决策点的斜率，队尾点永远不会被选中，出队。然后入队。

计算斜率 $k=\frac{y_2-y_1}{x_2-x_1}$ ，浮点数会丢精度，可以转化为乘法进行，当然不转化在正常精度范围内也可以。

核心代码：

for(int i=1;i<=n;i++)
	{
		// 队首小于斜率2*a[i] 的所有点都出队  斜率2*a[i]增大 前面斜率小的点不会再次成为最优决策点 
		//保证队列中有两个点 
		while(head<tail && cal(que[head],que[head+1])<2*a(i))head++;
		
		dp[i]=getval(i,que[head]);  //队首q[head]为最优决策j
		 
		while(head<tail && cal(que[tail-1],que[tail])>cal(que[tail],i))tail--;  //队尾形成上凸包，队尾出队
		
		que[++tail]=i; 
	}

完整代码：点击

例2：[APIO2010]特别行动队

状态转移方程：

$f[i]=max(f[j]+a*(sum[i]-sum[j])^2+b*(sum[i]-sum[j])+c)$

也会出现 $i,j$ 的乘积项，本题直线斜率为负数，使得截距最大，维护一个相邻点斜率单调递减“上凸壳”。

例3：任务安排

$subtask1:$ $P2365$任务安排1

数据范围：$1 \leq N \leq 5000, 1 \leq S \leq 50, 1 \leq T_i,C_i \leq 100$

解法一：

设 $f[i,j]$ 表示前 $i$ 个任务分成 $j$ 批次执行的最小费用，则第 $j$ 批任务完成的时间就是 $j*S+sumT[i]$ ,状态转移方程就是

$f[i,j]=min_{0 \leq k <i}\{ f[k,j-1]+(S*j+sumT[i])*(sumC[i]-sumC[k]) \}$

$sumT[i]$ 是时间 $t[]$ 前缀和，$sumC[i]$ 是系数$c[]$ 的前缀和。

时间复杂度是 $O(n^3)$，会超时.

解法二

在执行一批任务时，无法知道前面启动了几次，如果增加一个维度记录之前启动次数，就是解法一，时间复杂度太高。但是这批任务启动一次，对后面所有任务都会增加 $S$ 的时间，那对后面的影响就是增加 $S*(sumC[n]-sumC[i])$ 的代价，设 $F[i]$ 表示前 $i$ 个任务分成若干批执行的最小费用，状态转移方程为：

$F[i]=min_{0 \leq j <i}\{ f[j]+sumT[i]*(sumC[i]-sumC[j])+S*(sumC[n]-sumC[j])\}$

任务 $j+1 \sim i$ 是同批执行的任务，这个批次执行会对后面 $i+1 \sim n$ 任务产生影响，增加 $S*(sumC[n]-sumC[i])$ 的代价，提前把对后面的影响补充进来，“提前计算”。

时间复杂度为 $O(n^2)$。

参考代码：

#include<bits/stdc++.h>
using namespace std;
const int N=5005;
int n,s;
long long t[N],c[N],sumt[N],sumc[N];
long long f[N];
int main()
{
   cin>>n>>s;
   for(int i=1;i<=n;i++)
   {
   	cin>>t[i]>>c[i];
   	sumt[i]=sumt[i-1]+t[i];
   	sumc[i]=sumc[i-1]+c[i];
   }
   memset(f,0x3f,sizeof(f));
   f[0]=0;
   for(int i=1;i<=n;i++)
   	for(int j=0;j<i;j++)
   		f[i]=min(f[i],f[j]+sumt[i]*(sumc[i]-sumc[j])+s*(sumc[n]-sumc[j]));
   cout<<f[n];
   return 0;
}

$subtask2:$ $ACwing301$任务安排2

数据范围：$1 \leq N \leq 3*10^5, 1 \leq S ,T_i,C_i \leq 512$

当 $n$ 范围扩大， $O(n^2)$ 会超时，观察状态转移方程，$1D/1D$ 转移 $i$ 和 $j$ 有乘积项，可以使用斜率优化。

$F[j]= (sumT[i]+S)*sumC[j]+F[i]-sumT[i]*sumC[i]+S*sumC[n]$

$x(j)=sumC[j],y(j)=F[j]$,斜率 $k=sumT[i]+S$,截距 $F[i]-sumT[i]*sumC[i]+S*sumC[n]$

由于 $T_i >0$ ,斜率 $sumT[i]+S$ 单调递增，可以删除队首斜率小的决策点，维护一个单调递增的下凸壳就可以了。

参考代码：点击

$subtask3:$ $P5785$任务安排3

数据范围：$1 \leq N \leq 3*10^5, 1 \leq S ,C_i \leq 512, -512 \leq T_i \leq 512$

根据 $subtask2$ 得到：

$F[j]= (sumT[i]+S)*sumC[j]+F[i]-sumT[i]*sumC[i]+S*sumC[n]$

$x(j)=sumC[j],y(j)=F[j]$ ,斜率 $k=sumT[i]+S$,截距 $F[i]-sumT[i]*sumC[i]+S*sumC[n]$

由于 $T[i]$ 可以为负数,斜率 $sumT[i]+S$ 不再单调，不能删除队首，可以二分查找第一个大于等于斜率 $sumT[i]+S$ 的位置 $j$ ,此时 $j$ 就是最优决策位置。

核心代码：

int binary_search(int i,int k)
{
   if(head==tail)return que[head];
   int ans=0;
   for(int j=1<<30;j;j>>=1)
   	if( ans+j<tail && que[ans+j] < i && cal(que[ans+j],que[ans+j+1])<k)ans+=j;
   
   return que[ans+1];
} 
signed main()
{
   cin>>n>>S;
   for(int i=1;i<=n;i++)
   {
   	int t,c;
   	cin>>t>>c;
   	sumT[i]=sumT[i-1]+t;
   	sumC[i]=sumC[i-1]+c;
   }
   head=tail=1;
   que[1]=0;
   f[0]=0;
   
   for(int i=1;i<=n;i++)
   {
   	//while(head<tail && cal(que[head],que[head+1])<sumT[i]+S)head++;由于斜率不单调，不能删除队首
   	//二分找到一次大于斜率sumT[i]+S的位置p
   	int p=binary_search(i,sumT[i]+S); 
   	
   	//f[i]=getval(i,que[head]);由于斜率不单调 就不一定是队首了 
   	f[i]=getval(i,p);
   	
   	//while(head<tail && cal(que[tail-1],que[tail])>=cal(que[tail],i))tail--;
   	//精度不够 
   	while(head<tail && (y(que[tail])-y(que[tail-1]))*(x(i)-x(que[tail]))>=(y(i)-y(que[tail]))*(x(que[tail])-x(que[tail-1])))tail--;
   	que[++tail]=i;		
   }
   cout<<f[n];

   return 0;
}

详细代码：点击

$subtask4:$ [任务安排4]

• $T_i$ 为正，但 $C_i$ 可能是负数，如何处理？

$x(j)=sumC[j]$，斜率 $k=sumT[i]+S$ ，$T_i$ 为正，斜率递增，$x(j)$ 不一定单调。可以倒序 DP,设计一个状态转移方程，改变横纵坐标，即斜率成为 $x$，转化为任务3。

• $T_i,C_i$ 都为负数，如何处理？

$x$ 和斜率都不单调，意味着要在凸壳上任意位置动态插入顶点、动态查询前驱后继，此时用平衡树来为维护凸壳。

典型例题 [CEOI2017]Building Bridges，$x$ 和斜率都不单调。 当然此题还可以CDQ分治、李超线段树去做。

小结：

任务安排 1 [Loj10184] [P2365] 优化状态定义及转移， $O(n^2)$

任务安排 2 [Loj10185] [Poj1180] $x(j)=sumC[j]$ 及斜率 $k=sumT[i]+S$ 都单增。

斜率递增，队首点会永久失效，队首出队，$x$ 递增，点 $i$ 是新加入的决策点，与队尾斜率也要递增，否则队尾点永远不可能是最优决策点，此时队尾出队，直至队尾与点 $i$ 斜率递增。

任务安排 3 [SDOI2012] [P5785] [Loj10186] [Bzoj2726]

$x(j)$ 递增，斜率 $k=sumT[i]+S$ 不单调。

由于斜率不单调，队首不能出队，在斜率递增队列中二分查找下凸包最优点，即点 $p$ 与下一个点 $p+1$ 斜率大于直线斜率 $k$ 。

任务安排 4 都不单调，需要动态查询前驱后继、动态插入，平衡树维护凸壳。

---

练习题小结：

1.$X(j)$ 与 $k[i]$ 均单调的例子

• 玩具装箱 toy [HNOI2008] [P3195]

• 土地征用 Land Acquisition G [P2900]

• 征途 [SDOI2016] [P4072]

• Cats Transport [CF311B]

• 摆渡车 [NOIP2018] [P5017]

• 仓库建设 [ZJOI2007] [P2120]

• 序列分割 [APIO2014] [P3648]

• 锯木厂选址 [CEOI2004] [P4360]

• 特别行动队 [APIO2010] [P3628]

• 国王饮水记 [NOI2016] [P1721]

2.$X(j)$ 单调 $k[i]$ 不单调

• 任务安排 3 [SDOI2012] [P5785] [Loj10186] [Bzoj2726]

• 购票 [NOI2014] [P2305] （X(j) 单调 k[i] 不单调。树上转移）

3.$X(j)$ 与 $k[i]$ 均不单调

• Building Bridges [CEOI2017] [P4655]

• 货币兑换 [NOI2007] [P4027]

学习完毕

{{ select(1) }}

• YES
• NO