LibreOJ 10189 「ZJOI2007」仓库建设

我们可以把问题抽象一下：
把一个序列划分成若干段，如果某一段对应的区间为 [l,r]，则代价为 cr+r∑i=lpi(xr−xi)。
于是得到转移方程 fi=min0≤j<i(fj+ci+i∑k=j+1pk(xi−xk))。

设 si=i∑j=1pi,Si=i∑j=1pixi。
则原式变为 fi=min0≤j<i(fj+ci+(si−sj)xi−(Si−Sj))。

对于 0≤k<j<i，设此时选择 j 更优，即 fj+ci+(si−sj)xi−(Si−Sj)≤fk+ci+(si−sk)xi−(Si−Sk)。
整理一下，有 fj+ci+(si−sj)xi−(Si−Sj)≤fk+ci+(si−sk)xi−(Si−Sk)fj−sjxi+Sj≤fk−skxi+Sk(fj+Sj)−(fk+Sk)≤(sj−sk)xi(fj+Sj)−(fk+Sk)sj−sk≤xi

单调队列维护下凸包即可。

代码：

#include <cstdio>
using namespace std;
const int N = 1e6;
int n;
int q[N + 5],head,tail;
int x[N + 5],p[N + 5],c[N + 5];
long long s[N + 5],S[N + 5],f[N + 5];
inline double slope(int x,int y)
{
    return (double)(f[x] + S[x] - f[y] - S[y]) / (s[x] - s[y]);
}
int main()
{
    scanf("%d",&n);
    for(register int i = 1;i <= n;++i)
        scanf("%d%d%d",x + i,p + i,c + i),s[i] = s[i - 1] + p[i],S[i] = S[i - 1] + (long long)p[i] * x[i];
    q[head = tail = 1] = 0;
    for(register int i = 1;i <= n;++i)
    {
        for(;head < tail && slope(q[head],q[head + 1]) <= x[i];++head);
        f[i] = f[q[head]] + c[i] + (s[i] - s[q[head]]) * x[i] - S[i] + S[q[head]];
        for(;head < tail && slope(q[tail - 1],q[tail]) >= slope(q[tail],i);--tail);
        q[++tail] = i;
    }
    printf("%lld\n",f[n]);
}