斜率优化学记笔记

[例题](https://www.luogu.com.cn/problem/P3195)

考虑朴素做法:

$f_i$表示把前$i$个玩具装箱所需的最小费用，$s_i$为$c_i$的前缀和，则有：

$$f_i=\min\limits_{j=1}^i(f_{j-1}+(i-j+s_i-s_{j-1}-L)^2)$$

令$g_i=i+s_i-L,x_i=j+s_{j-1}$,则有：

$$f_i=\min\limits_{j=1}^i(f_{j-1}+(g_i-x_j)^2)=\min\limits_{j-1}^i(f_{j-1}+g_i^2-2g_ix_j+x_j^2)$$

时间复杂度$O(n^2)$肯定过不了

考虑斜率优化：

令$w_{i,j}=f_{j-1}+g_i^2-2g_ix_j+x_j^2$

思考当$j2>j1$且$w_{i,j2}<w_{i,j1}$时应满足什么情况？

会有：$f_{j2-1}+g_i^2-2g_ix_{j2}+x_{j2}^2<f_{j1-1}+g_i^2-2g_ix_{j1}+x_{j1}^2$

令$y_i=f_{i-1}+x_i$

化简得：$\dfrac{y_{j2}-y_{j1}}{x_{j2}-x_{j1}}<2g_i$

使用单调队列维护：

令$T(j_1,j_2)=\dfrac{y_{j2}-y_{j1}}{x_{j2}-x_{j1}}$

因为$g_i$单调递增，所以若$T(j_1,j_2)<2g_i$则$T(j_1,j_2)<2g_{i+1}$所以$j_1$将没有任何作用，则$j_1$可以踢出队列

设剩下$k_1,k_2...k_l$满足任意$T(k_x,k_{x+1})>2g_i$

则我们可知$k_1$是最优的

因为$T(k_1,k_2)>2g_i$，所以$k_1$比$k_2$优

$T(k_2,k_3)>2g_i$，所以$k_2$比$k_3$优

$......$

所以$k_1$最优

还有一个性质，若$k_2$想在单调队列中最优，则应满足$T(k_1,k_2)<2g_i,T(k_2,k_3)>2g_i$，即$T(k_2,k_3)>T(k_1,k_2)$

总结，这个单调队列里面的数应满足：

$2g_i<T(k_1,k_2)<T(k_2,k_3)<......<t(k_{l-1},k_l)$

上代码：

```cpp
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=5e4+50;
ll n,L,head=1,tail=0;
ll c[N],s[N],f[N],q[N];
ll g(ll i){return i+s[i]-L;}
ll x(ll i){return i+s[i-1];}
ll y(ll i){return f[i-1]+x(i)*x(i);}
ll T(ll i1,ll i2){return (y(i2)-y(i1))/(x(i2)-x(i1));}
int main()
{
scanf("%lld %lld",&n,&L);
for(ll i=1;i<=n;i++)
{
scanf("%lld",&c[i]);
s[i]=s[i-1]+c[i];
}
for(ll i=1;i<=n;i++)
{
while(head<tail&&T(q[tail-1],q[tail])>T(q[tail],i)) tail--;
//不满足T(j1,j2)<T(j2,j3)的情况，则j2无用，踢出j2
q[++tail]=i;
while(head<tail&&T(q[head],q[head+1])<2*g(i)) head++;
//不满足T(j1,j2)>2g[i]的情况，则j2比j1优，踢出j1
f[i]=f[q[head]-1]+(g(i)-x(q[head]))*(g(i)-x(q[head]));
}
printf("%lld\n",f[n]);
return 0;
}
```