BZOJ 1096 [ZJOI2007]仓库建设 斜率优化

2/22/2017来源:ASP.NET技巧人气:4102

#include <cstdio> #include <cstring> #include <algorithm> #include <cstring> #include <cmath> #define MAXN 1000005 #define N 100 #define LL long long #define INF 1000000005 #define max(a,b) ((a)>(b)?(a):(b)) #define min(a,b) ((a)<(b)?(a):(b)) using namespace std; const double eps = 1e-8; /* f[i]=max{f[j]/(a[j]*rate[j]+b[j])*rate[j]*a[i]+f[j]/(a[j]*rate[j]+b[j])*b[i]} x[j]=f[j]/(a[j]*rate[j]+b[j])*rate[j] y[j]=f[j]/(a[j]*rate[j]+b[j]) ->f[i]=x[j]*a[i]+y[j]*b[i] ->y[j]=f[i]/b[i]-x[j]*a[i]/b[i] */ LL read() { LL t=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){t=t*10+ch-'0';ch=getchar();} return t*f; } LL n,l=1,r=0; LL f[MAXN],q[MAXN],b[MAXN],c[MAXN],p[MAXN],x[MAXN],s[MAXN]; double getk(int i,int j) { return (double)(f[i]+b[i]-f[j]-b[j])/(double)(s[i]-s[j]); } int main() { n=read(); for(int i=1;i<=n;i++) x[i]=read(),p[i]=read(),c[i]=read(); for(int i=1;i<=n;i++) s[i]=s[i-1]+p[i],b[i]=b[i-1]+x[i]*p[i]; q[++r]=0; for(int i=1;i<=n;i++) { while(l<r&&getk(q[l],q[l+1])<x[i]) l++; int j=q[l]; f[i]=f[j]+(s[i]-s[j])*x[i]-(b[i]-b[j])+c[i]; while(l<r&&getk(i,q[r])<getk(q[r],q[r-1])) r--; q[++r]=i; } PRintf("%lld",f[n]); return 0; }