前言

近几日回归竞赛后，便开始学些新东西了（对于蒟蒻来说）。这几天就连续的更新一下自己对斜率优化的学习过程。

1.思想

在一些常见的DP题中，可能会出现形如\(f[i]=\min/\max(f[j]+(sum[i]-sum[j])^2\)的转移方程式。
这时，我们就可以把后面的二次项展开：

\(f[i]=f[j]+sum[i]^2+sum[j]^2+2*sum[i]*sum[j]\)

\(f[j]+sum[j]^2=2*sum[i]*sum[j]+sum[i]^2+f[i]\)

再将\(2*sum[i]\)看做斜率，\(f[j]+sum[j]\)看做\(y\)，\(sum[j]\)看做\(x\)，则\(f[i]+sum[i]^2\)就成了截距，由于斜率不变，我们就用一个单调队列来维护之前的决策点，再将该斜率的直线从下到上平移，找到斜率最小的点。所以我们既要维护一个下凸包。

2.实现

利用单调队列维护当前的决策点构成的凸包，在遍历到\(i\)时，先将斜率小于当前斜率的决策点全部删去。然后对头的点就是当前的最优决策点，更新当前值后，在队尾加点时保证斜率的单调递增即可。

如果要维护一个上凸包就反着来（emm）

1.去除队头，比较斜率；

2.更新答案；

3.加入队伍，维护单调性质；

3.典例

1.[HNOI2008]玩具装箱 ( 模板斜率优化DP )

先理解一下题意，总而言之就是划分一个序列，满足贡献值最小的情况。

转移方程：\(f(x)=\min_{i=1}^{x-1}(f(i)+(j-i+\sum^j_{k=i}c[k]-L)^2)\)

把\(b[j]\)看成x,斜率就是\(2?a[i]\)，截距就是\(dp[i]-a[i]^2\)。

且斜率是单调递增的。

然后就要寻找最小的截距，就使用单调队列维护下凸包了~~

while(head

#include
using namespace std;
#define db double
#define ll long long
const int maxn=50010;
int n,L;
db sum[maxn],dp[maxn];
int head,tail,Q[maxn];
inline db a(int i){
	return sum[i]+i;
}
inline db b(int i){
	return a(i)+L+1;
}
inline db X(int i){
	return b(i);
}
inline db Y(int i){
	return dp[i]+b(i)*b(i);
}
inline db slope(int i,int j){
	return (Y(i)-Y(j))/(X(i)-X(j));
}
int main(){
	scanf("%d%d",&n,&L);
	for(int i=1;i<=n;i++){
		scanf("%lf",&sum[i]);
		sum[i]+=sum[i-1];
	}	
	head=tail=1;
	for(int i=1;i<=n;i++){
		while(head

#include
using namespace std;
int n;
const int N=1e5;
long long dp[N],s[N],wdis[N],dis[N];
long long tot;
int q[N];
inline double calc(int j,int k){
	return (double) (dis[j]*s[j]-dis[k]*s[k])/(s[j]-s[k]);
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		int a,b;
		cin>>s[i]>>dis[i];
		s[i]=s[i-1]+s[i];
		tot+=s[i]*dis[i];
	}
	//cout<=1;i--){
		dis[i]=dis[i+1]+dis[i];
	//	cout<=dis[i]) ++head;
		ans=min(ans,tot-dis[q[head]]*s[q[head]]-dis[i]*(s[i]-s[q[head]]));
		while(head=calc(q[tail-1],q[tail]))--tail;
		q[++tail]=i;
	}
	cout<

#include
#define y(i) (dp[i]+a*sum[i]*sum[i]-b*sum[i])
#define int long long
#define re register
using namespace std;
int a,b,c;
int n;
const int N=1e6+100;
int sum[N];
int q[N];
int dp[N];
inline double slope(int j,int k){
	return 1.0*(y(j)-y(k))/(sum[j]-sum[k]);
} 
signed main(){
	scanf("%lld",&n);
	scanf("%lld %lld %lld",&a,&b,&c);
	for(re int i=1;i<=n;i++){
		scanf("%lld",&sum[i]);
		sum[i]+=sum[i-1];
	}
	re int head=1,tail=1;
	for(re int i=1;i<=n;i++){
		while(head2*a*sum[i]) head++;
		dp[i]=(1ll*(sum[i]-sum[q[head]])*(sum[i]-sum[q[head]])*a+1ll*b*(sum[i]-sum[q[head]])+c+dp[q[head]]);
		while(head=slope(q[tail-1],q[tail])) --tail;
		q[++tail]=i;
	}
	printf("%lld\n",dp[n]);
	
	return 0;
}