来自 这篇笔记 第5部分。

注：由于AcWing的LaTeX有点奇怪，所以文中所有应该用 {} 表示的minmax全部采用小括号

题目链接： AcWing
luogu

题意

有 $n$ 个工厂，由高到低分布在一座山上，工厂 $1$ 在山顶，工厂 $n$ 在山脚。第 $i$ 个工厂目前有成品 $p_i$ 件，在第 $i$ 个工厂位置建立仓库的费用是 $c_i$. 对于没有建立仓库的工厂，其产品被运往其他的仓库，产品只能往山下运（只能运往编号更大的工厂的仓库），一件产品运送一个单位距离的费用是 $1$.假设建立的仓库容量都足够大。工厂 $i$ 与 $1$ 的距离是 $x_i$，问总费用最小值。

思路

$$ f_i=min(f_j+x_i\times \sum_{l=j+1}^i(p_l)-\sum_{l=j+1}^i(x_l\times p_l) )+c_i,0\leq j<i $$
前缀和，设 $sp_i=\sum_{j=1}^i p_j,s_i=\sum_{j=1}^i p_j\times x_j$
得到新的式子：
$$ f_i=f_j+x_i\times (sp_i-sp_{j})-(s_i-s_j)+c_i $$
然后斜率优化：
$$ f_j+s_j=x_i\times sp_j+(f_i+s_i-c_i-x_i\times sp_i) $$

代码

#include <bits/stdc++.h>
#define ll long long
#define lb long double
using namespace std;
const int N=1e6+10;
int n,q[N],h,t;
ll x[N],p[N],c[N],f[N],sp[N],s[N];

ll X( int num ){ return sp[num]; }
ll Y( int num ){ return f[num]+s[num]; }
lb slope( int n1,int n2 ) { return (lb)(Y(n2)-Y(n1))/(X(n2)-X(n1)); }

int main()
{
        scanf( "%d",&n );
        for ( int i=1; i<=n; i++ )
                scanf( "%lld%lld%lld",&x[i],&p[i],&c[i] );
        sp[0]=s[0]=0;
        for ( int i=1; i<=n; i++ )
                sp[i]=sp[i-1]+p[i],s[i]=s[i-1]+p[i]*x[i];

        h=t=1; q[1]=0;
        for ( int i=1; i<=n; i++ )
        {
                while ( h<t && slope(q[h],q[h+1])<=(lb)x[i] ) h++;
                f[i]=f[q[h]]+x[i]*(sp[i]-sp[q[h]])-(s[i]-s[q[h]])+c[i];
                while ( h<t && slope(q[t-1],q[t])>=slope(q[t],i) ) t--;
                t++; q[t]=i;
        }

        printf( "%lld",f[n] );
}