斜率优化
斜率优化是一种对于形如 \(F_{i}=\min/\max\{F_j+...\}\) 的转移方程式，将其结构变换从而与几何联系起来，转化为坐标系内求凸包切线的问题。
结合例题讲解。
【例1】任务安排 1
说明：题目中的 \(f\) 被我篡改成了 \(c\)。
列出朴素转移方程。设 \(F(i,j)\) 表示前 \(i\) 物品分成 \(j\) 段的最小费用，\(C[i],T[i]\) 分别为 \(c_i,t_i\) 前缀和。
\[F(i,j)=\min_{0\le k时间复杂度 \(O(n^3)\)。
一个常用的技巧叫做 费用提前计算：考虑到
- 题目并未要求具体分几段，因此 \(j\) 维理论可以省掉
- \(k+1\sim i\) 多分成一段，造成的影响 是后面所有的物品完成时间 \(+S\)
因此，可以写出
\[F[i]=\min_{0\le j相当于是把费用给在产生时就计算了。由于 ________________________（坑待填），这种优化方式是不会造成错误决策的。
时间复杂度 \(O(n^2)\)，可以通过。
#include
using namespace std;
const int N=5005;
int n,S,t[N],c[N];
long long f[N];
int main(){
cin>>n>>S;
for(int i=1;i<=n;i++)cin>>t[i]>>c[i],t[i]+=t[i-1],c[i]+=c[i-1];
memset(f,0x3f,sizeof(f));
f[0]=0;
for(int i=1;i<=n;i++)
for(int j=0;j 【例2】任务安排 2
在【例1】基础上，\(n\le 3*10^5\)。
先把 \(\min\) 去掉。
\[F[i]= F[j]+(C[i]-C[j])*T[i]+S*(C[n]-C[j]) \]再展开。
\[F[i]=F[j]+C[i]T[i]-C[j]T[i]+SC[n]-SC[j] \]再将只关于 \(j\) 的、同时关于 \(i,j\) 的、常数项区分开。由于所在是 \(i\)，因此含 \(i\) 的（例如 \(T[i],C[i]\)）就等同不变量（常数）。
只关于 \(j\) 的：放在等号左边。
\[F[j]=C[j](S+T[i])+F[i]-C[i]T[i]-SC[n] \]这样，可以看成一个一次函数 \(y=kx+b\)。其中 \(y=F[j],k=S+T[i],x=C[j],b=F[i]-C[i]T[i]-SC[n]\)。
只需要最小化截距，就相当于最小化 \(F[i]\)。
考虑这个式子的含义，发现斜率是定值，而必须经过坐标系的若干点 \((C[j],F[j])\)。也就是一条斜率一定的直线在坐标系内自下而上移动，碰到的第一个点就是使截距最小化的点。这一步叫做线性规划。
那么求这些点的凸包，一个容易发现的结论是该直线一定经过下凸壳上的点。
考虑决策单调性。发现 \((C[j],F[j])\) 随着 \(j\) 的增大，\(C[j]\) 增大，所以可以一般地维护下凸壳，利用一个单调数据结构。我们可以用单调队列。
在本题中，每确定一个 \(F[i]\)，就将 \((C[i],F[i])\) 从队尾加入下凸壳并维护下凸壳。同时，观察到 \(S+T[i]\) 是递增的，因此切点左侧的凸壳点都可以丢掉，所以可以逐一弹掉满足 \(q[l],q[l+1]\) 的连线斜率 \(\le S+T[i]\) 的队头 \(l\)。 总复杂度 \(O(n)\)。
【例3】任务安排 3
与【例2】的唯一区别为：\(t_i\) 可以为负数。
这说明斜率 \(S+T[i]\) 不再单调递增。所以必须保留所有凸壳点。
而只需要在单调队列（此时也可以替换为单调栈）里二分一个最靠前的点 \(q[mid]\)，使得 \(q[mid],q[mid+1]\) 所连接的线段的斜率大于 \(S+T[i]\)，就能找到切点 \(q[mid]\)。
#include
#define int long long
using namespace std;
const int N=3e5+5;
int n,S,tp,l=1,r=0,t[N],c[N],q[N],f[N];
signed main(){
cin>>n>>S;
for(int i=1;i<=n;i++)cin>>t[i]>>c[i],t[i]+=t[i-1],c[i]+=c[i-1];
q[++r]=0;
for(int i=1;i<=n;i++){
int L=l-1,R=r,mid;
while(L>1;
if((f[q[mid+1]]-f[q[mid]])>(S+t[i])*(c[q[mid+1]]-c[q[mid]]))R=mid;
else L=mid;
}
f[i]=f[q[R]]+(c[i]-c[q[R]])*t[i]+S*(c[n]-c[q[R]]);
while(r>l&&(c[q[r]]-c[q[r-1]])*(f[i]-f[q[r-1]])-(c[i]-c[q[r-1]])*(f[q[r]]-f[q[r-1]])<=0)r--;
q[++r]=i;
}
cout< 一个非常容易错的点是凸壳操作的取等问题，参见 here。
【例4】玩具装箱
斜率优化模板题。属于【例2】类型，\(O(n)\)。在上一题中，我们将斜率的分母乘到了另一边，十字相乘了，但这样有两个条件：
-
分母是正数
-
不会爆 LL
本题不满足第二个条件，所以采用相对不保险，其实算保险的浮点数斜率。
#include
#define int long long
#define y(i) (f[i]+s[i]*s[i])
using namespace std;
const int N=5e4+5;
int n,L,l=1,r,s[N],q[N],f[N];
signed main(){
cin>>n>>L,L++;
for(int i=1;i<=n;i++)cin>>s[i],s[i]+=s[i-1]+1;
q[++r]=0;
for(int i=1;i<=n;i++){
while(l 【例5】CF311B Cats Transport
容易想到将每只猫以 \((t_i,y_i)\) 的形式放到坐标系里，而 feeder 则是一条斜率 =1 的直线，其中 \(y_i=D_{h_i}\)，\(D_{h_i}\) 表示 0 到 \(h_i\) 的距离，则题意转为
用至多 \(p\) 条直线来划分这 \(n\) 个点，使得代价最小。代价的计算方式为过该点作一条平行横轴直线，直线与右侧 feeder 直线的第一个交点到该点的距离。
首先显然最优情况下一定 feeder 直线是要过一个点的。考察这个点，假如记作 \((X,Y)\)，那么 \((x,y)\) 分给他的代价为 \((X-x+y-Y)=(X-Y)-(x-y)\)。
因此先将点排好序：
bool operator<(cat a,cat b){
return a.t-a.y这样就可以 dp 了。
\[F(w,i)=\min_{0\le j展开得到
\[F(w,i)=F(w-1,j)+(i-j)*(t_i-y_i)-T[i]+T[j]+Y[i]-Y[j] \]整理得
\[F(w-1,j)+T[j]-Y[j]=(t_i-y_i)*j+F(w,i)-(t_i-y_i)*i+T[i]-Y[i] \]就可以斜率优化了。这时再看重载运算符，发现刚好保证了斜率单调性，是不是很巧妙呢？
这题一定不能把分母乘到另一边因为两者都不满足。
#include
#define int long long
using namespace std;
const int N=1e5+5;
int n,m,p,h[N],d[N],T[N],Y[N],f[2][N],q[N];
struct cat{
int t,y;
}a[N];
bool operator<(cat a,cat b){
return a.y-b.y+b.t-a.t>0;
}
signed main(){
cin>>m>>n>>p;
for(int i=2;i<=m;i++)cin>>d[i],d[i]+=d[i-1];
for(int i=1;i<=n;i++)cin>>h[i]>>a[i].t,a[i].y=d[h[i]];
sort(a+1,a+n+1);
for(int i=1;i<=n;i++)T[i]=T[i-1]+a[i].t,Y[i]=Y[i-1]+a[i].y;
memset(f,0x3f,sizeof(f));
int ans=1e18;
f[0][0]=0;
for(int w=1;w<=p;w++){
f[w&1][0]=0;
int l=1,r=0;q[++r]=0;
for(int i=1;i<=n;i++){
while(l=1.0*((f[w&1^1][i]+T[i]-Y[i])-(f[w&1^1][q[r-1]]+T[q[r-1]]-Y[q[r-1]]))/(i-q[r-1]))r--;
q[++r]=i;
}
ans=min(ans,f[w&1][n]);
}
cout<