bzoj1096

题解：

斜率优化dp

代码：

#include<bits/stdc++.h> 
typedef long long ll;
const int N=1000005;
using namespace std;
int n,l,r,q[N];
ll p[N],x[N],c[N],f[N],b[N],sum[N];
double slop(int k,int j)
{
    return double(f[j]-f[k]+b[j]-b[k])/double(sum[j]-sum[k]);
}
int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++)scanf("%d%d%d",&x[i],&p[i],&c[i]);
    for (int i=1;i<=n;i++)
     {
        sum[i]=sum[i-1]+p[i];
        b[i]=b[i-1]+p[i]*x[i];
     }
    for (int i=1;i<=n;i++)
     {
        while (l<r&&slop(q[l],q[l+1])<x[i])l++;
        int t=q[l];
        f[i]=f[t]-b[i]+b[t]+(sum[i]-sum[t])*x[i]+c[i];
        while (l<r&&slop(q[r-1],q[r])>slop(q[r],i))r--;
        q[++r]=i;
     }
    printf("%lld",f[n]);
    return 0;
}