【算法】DP+斜率优化
【题解】状态转移方程：f[i]=min(f[j]+g(i+1,j-1))+c[i]
关键在于如何O(1)计算g(i+1,j-1)。
推导过程：http://blog.csdn.net/PoPoQQQ/article/details/40504949
当d(j,k)中j<k且k更优时，得到斜率不等式：
(f[j]-f[k]+sumpx[j]-sumpx[k])/(sump[j]-sump[k])<x[i]
于是斜率优化。
斜率优化：http://www.cnblogs.com/onioncyc/p/6113450.html
【细节】
1.是while不是if。。。
2.p[i]*x[i]*1ll。。。
3.转double运算优先度高于除法的样子。
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
const int maxn=;
int q[maxn],x[maxn],p[maxn],c[maxn],n;
ll f[maxn],sump[maxn],sumpx[maxn];
double calc(int j,int k)
{return (double)(f[j]-f[k]+sumpx[j]-sumpx[k])/(sump[j]-sump[k]);}//important3
ll g(int i,int j)
{return x[i]*(sump[i-]-sump[j])-(sumpx[i-]-sumpx[j]);}
int main()
{
scanf("%d",&n);
sump[]=sumpx[]=;
for(int i=;i<=n;i++)
{
scanf("%d%d%d",&x[i],&p[i],&c[i]);
sump[i]=sump[i-]+p[i];
sumpx[i]=sumpx[i-]+1ll*p[i]*x[i];//important2
}
int head=,tail=;q[]=;f[]=;
for(int i=;i<=n;i++)
{
while(head<tail&&calc(q[head],q[head+])<x[i])head++;
f[i]=f[q[head]]+g(i,q[head])+c[i];
while(head<tail&&calc(q[tail-],q[tail])>calc(q[tail],i))tail--;//important1
q[++tail]=i;
}
printf("%lld",f[n]);
return ;
}