【bzoj1096】仓库建设 斜率优化dp

AC通道：http://www.lydsy.com/JudgeOnline/problem.php?id=1096

【题解】

设输入的三个数组为a，b，c

sumb维护b数组的前缀和，sumab维护a*b的前缀和。

则状态转移方程：f[i]=min{f[j]+c[i]+a[i]*(sumb[i-1]-sum[j])-(sumab[i-1]-sumab[j])}

斜率表达式：(f[j]+sumab[j]-f[k]-sumab[k])/(sumb[j]-sumb[k])>a[i]

/*************

  bzoj 1096

  by chty

  2016.11.15

*************/

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<ctime>

#include<algorithm>

using namespace std;

typedef long long ll;

#define FILE "read"

#define MAXN 1000100

#define up(i,j,n)  for(ll i=j;i<=n;i++)

namespace INIT{

	char buf[1<<15],*fs,*ft;

	inline char getc() {return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;}

	inline ll read(){

		ll x=0,f=1;  char ch=getc();

		while(!isdigit(ch))  {if(ch=='-')  f=-1;  ch=getc();}

		while(isdigit(ch))  {x=x*10+ch-'0';  ch=getc();}

		return x*f;

	}

}using namespace INIT;

ll n,head,tail,a[MAXN],b[MAXN],c[MAXN],f[MAXN],sumb[MAXN],sumab[MAXN],q[MAXN];

void init(){

	n=read();

	up(i,1,n) a[i]=read(),b[i]=read(),c[i]=read();

	up(i,1,n) sumb[i]=sumb[i-1]+b[i],sumab[i]=sumab[i-1]+a[i]*b[i];

}

inline double slop(ll j,ll k) {return (double)((f[j]+sumab[j])-(f[k]+sumab[k]))/(double)(sumb[j]-sumb[k]);}

void solve(){

	up(i,1,n){

		while(head<tail&&slop(q[head],q[head+1])<a[i])  head++;

		ll t=q[head];

		f[i]=f[t]+c[i]+a[i]*(sumb[i-1]-sumb[t])-(sumab[i-1]-sumab[t]);

		while(head<tail&&slop(q[tail-1],q[tail])>slop(q[tail],i))  tail--;

		q[++tail]=i;

	}

	printf("%lld\n",f[n]);

}

int main(){

	freopen(FILE".in","r",stdin);

	freopen(FILE".out","w",stdout);

	init();

	solve();

	return 0;

}