省选专练之斜率优化[ZJOI2007]仓库建设

乍一看不好维护前缀和

观察前缀关系：令  

有：贡献为 

暨拆开：

故设： 

对于朴素DP、

转移有：

设k为选中点

有：

消去相同项

不妨设 

有

完毕

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const double eps=1e-8;
const int N=1e6+1000;
typedef int INT;
#define int long long
int G[N];
int F[N];
int P[N];
int X[N];
int C[N];
int Q[N*3];
int head,tail;
int n;
double Y(int Id){
	return F[Id]*1.0-G[Id]*1.0;
}
double Xsum(int Id){
	return P[Id]*1.0;
}
double Slope(int k,int t){
	return ((double)Y(t)-Y(k))/(double)(Xsum(t)-Xsum(k));
}
INT main(){
//	freopen("1096.in","r",stdin);
//	freopen("1096.out","w",stdout);
	scanf("%lld",&n);
	for(int i=1;i<=n;i++){
		scanf("%lld%lld%lld",&X[i],&P[i],&C[i]);
		G[i]=G[i-1]-X[i]*P[i];
	}
	for(int i=1;i<=n;i++){
		P[i]+=P[i-1];
	}
	head=1;
	tail=0;
	Q[1]=0;
	for(int i=1;i<=n;i++){
		F[i]=C[i]+P[i-1]*X[i]+G[i-1]; 
		while(head<tail&&X[i]-Slope(Q[head],Q[head+1])>eps)head++;
		int Id=Q[head];
		F[i]=min(F[i],(F[Id]+(P[i-1]-P[Id])*X[i]+G[i-1]-G[Id]+C[i]));
		while(head<tail&&Slope(Q[tail-1],Q[tail])-Slope(Q[tail],i)>eps)tail--;
		tail++;
		Q[tail]=i;
//		cout<<F[i]<<'\n';
	}
	cout<<(int)F[n]<<'\n';
	return 0;
}