题意：

N个工厂，第i个工厂目前已有成品Pi件，在第i个工厂位置建立仓库的费用是Ci。对于没有建立仓库的工厂，其产品应被运往其他的仓库进行储藏，产品都只能运往编号更大的工厂的仓库，一件产品运送1个单位距离的费用是1。求最小总费用（建造费用+运输费用）。N最大10e6

题解：

斜率优化dp。我公式推错了3次QAQ

f[i]=max{f[j]+sigma(k,j+1,i)(x[i]-x[k])*p[k]+c[i]}

=max{f[j]+sigma(k,j+1,i)x[i]*p[k]-sigma(k,j+1,i)x[k]*p[k]+c[i]}

=max{f[j]+(sump[i]-sump[j])*x[i]-(sumxp[i]-sumxp[j])+c[i]}

=max{f[j]+sump[i]*x[i]-sump[j]*x[i]-sumxp[i]+sumxp[j]+c[i]}

f[j]+sump[i]*x[i]-sump[j]*x[i]-sumxp[i]+sumxp[j]+c[i]<f[k]+sump[i]*x[i]-sump[k]*x[i]-sumxp[i]+sumxp[k]+c[i]

f[j]-f[k]+sumxp[j]-sumxp[k]<sump[j]*x[i]-sump[k]*x[i]

(f[j]-f[k]+sumxp[j]-sumxp[k])/(sump[j]-sump[k])>x[i]（j在k前面）

注意开始是单调队列里要有一个f[0]，因为不需要一定在1处建仓库（本弱和标程对拍才发现这个错误，好弱啊！）

代码：

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #define inc(i,j,k) for(int i=j;i<=k;i++) 5 #define maxn 1000100 6 #define ll long long 7 using namespace std; 8  9 10 ll sump[maxn],sumxp[maxn],f[maxn],c[maxn],x[maxn]; int n,q[maxn],l,r;11 double calc(int j,int k){12     return (double)(f[j]-f[k]+sumxp[j]-sumxp[k])/(double)(sump[j]-sump[k]);13 }14 int main(){15     scanf("%d",&n); sump[0]=sumxp[0]=0;16     inc(i,1,n){17         ll p; scanf("%lld%lld%lld",&x[i],&p,&c[i]); sump[i]=sump[i-1]+p; sumxp[i]=sumxp[i-1]+x[i]*p;18     }19     l=0; r=0; q[l]=0; f[0]=0;20     inc(i,1,n){21         while(l
        
       
      
     

 

20160520