标题效果：特定n植物，其中一些建筑仓库，有一点使，假设没有仓库仓库向右仓库。最低消费要求

非常easy边坡优化……在此之前刷坡优化的情况下，即使这道题怎么错过

订购f[i]作为i点建设化妆i花费所有安置前的最低货

那里

公式编辑器就是爽啊~

令sump[i]为p[i]的前缀和

令sumxp[i]为p[i]*x[i]的前缀和

化简有

f[j] + sumxp[j] = x[i]*sump[j] + sumxp[i] - x[i]*sump[i] - C[i] + f[i]

当中

X[j]=sump[j]

Y[j]=f[j]+sumxp[j]

s[i]=x[i]

维护下凸包

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define M 1001001

using namespace std;

typedef long long ll;

typedef pair<ll,ll> abcd;

int n,X[M],P[M],C[M];

ll sumP[M],sumXP[M],f[M];

abcd q[M];int r,h;

double Get_Slope(const abcd &x,const abcd &y)

{

	return (double)(x.second-y.second)/(x.first-y.first);

}

void Insert(abcd x)

{

	while(r-h>1)

	{

		if( Get_Slope(q[r],x)<Get_Slope(q[r-1],q[r]) )

			q[r--]=q[0];

		else

			break;

	}

	q[++r]=x;

}

abcd Get_Ans(double s)

{

	while(r-h>1)

	{

		if(Get_Slope(q[h+1],q[h+2])<s)

			q[++h]=q[0];

		else

			break;

	}

	return q[h+1];

}

int main()

{

	int i;

	cin>>n;

	for(i=1;i<=n;i++)

		scanf("%d%d%d",&X[i],&P[i],&C[i]);

	for(i=1;i<=n;i++)

	{

		sumP[i]=sumP[i-1]+P[i];

		sumXP[i]=sumXP[i-1]+(ll)X[i]*P[i];

	}

	for(i=1;i<=n;i++)

	{

		Insert( make_pair(sumP[i-1],f[i-1]+sumXP[i-1]) );

		abcd p=Get_Ans(X[i]);

		f[i] = p.second + X[i]*sumP[i] - X[i]*p.first - sumXP[i] + C[i] ;

	}

	cout<<f[n]<<endl;

}