记录编号	62325	评测结果	AAAAAAAAAA
题目名称	[ZJOI 2007] 仓库建设	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	1.318 s
提交时间	2013-06-24 11:51:04	内存使用	34.61 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<deque>
#include<iomanip>
#include<cstring>
#include<stack>
#include<vector>
#include<fstream>
using namespace std;
typedef long long ll;
const ll SIZEN=1000001;
ll n;
ll d[SIZEN]={0};//d[i]表示i到山脚的距离
ll c[SIZEN]={0};//c[i]表示在i建仓库的费用
ll sp[SIZEN]={0};//sp[i]表示1~i的总产品数
ll sg[SIZEN]={0};//sg[i]表示1~i的g数之和
ll f[SIZEN]={0};
ll cons(ll x){//状态x,计算f[x]带上的常数
	return c[x]+sg[x]-d[x]*sp[x];
}
ll fig(ll x,ll i){//状态x,决策i除去关于x的常量
	return f[i]-sg[i]+d[x]*sp[i];
}
ll CX(ll x){
	return sp[x];
}
ll CY(ll x){
	return f[x]-sg[x];
}
ll uper(ll a,ll b,ll c){//c在线段ab上方
	ll x1=CX(b)-CX(a),x2=CX(c)-CX(a);
	ll y1=CY(b)-CY(a),y2=CY(c)-CY(a);
	return x1*y2>=x2*y1;
}
class MNQ{
public:
	deque<ll> S;
	void clf(ll x){
		while(S.size()>1&&fig(x,S[0])>=fig(x,S[1])) S.pop_front();
	}
	ll front(ll x){
		clf(x);
		return S[0];
	}
	bool sol(ll x){
		ll back=S.size()-1;
		return uper(S[back-1],x,S[back]);
	}
	void clb(ll x){
		while(S.size()>1&&sol(x)) S.pop_back();
	}
	void push_back(ll x){
		clb(x);
		S.push_back(x);
	}
}Q;
void work(void){
	ll i;
	Q.push_back(0);
	for(i=1;i<=n;i++){
		f[i]=fig(i,Q.front(i))+cons(i);
		//在i=23时,选取了决策20而非21
		Q.push_back(i);
	}
	printf("%lld\n",f[n]);
}
void init(void){
	scanf("%lld",&n);
	ll i;
	for(i=1;i<=n;i++) scanf("%lld%lld%lld",&d[i],&sp[i],&c[i]);
	ll temp=d[n];
	for(i=1;i<=n;i++) d[i]=temp-d[i];
	for(i=1;i<=n;i++) sg[i]=sg[i-1]+(sp[i]*d[i]);
	for(i=1;i<=n;i++) sp[i]+=sp[i-1];
}
int main(){
	freopen("storage.in","r",stdin);
	freopen("storage.out","w",stdout);
	init();
	work();
	return 0;
}