DZY 's BLOG

只是来除个草。。

这和当年CH上某cf赛制的题的B题很像。不过是这个的弱化版。

令f[i]表示第i个上面建仓库，1~i的都处理好了之后的最小花费。

那么f[i]=min{f[j]+w(j,i)}+c[i]

然后把w(j,i)化开：=p[j]*(x[i]-x[j])+p[j+1]*(x[i]-x[j+1])+...+p[i]*(x[i]-x[i])

=x[i]*p[j..i]-p[j]*x[j]+p[j+1]*x[j+1]+...+p[i]*x[i]

很明显前后两项都可以用前缀和数组O(1)出来。sp[i]=p[1..i],spx[i]=p[1]*x[1]+..+p[i]*x[i]

可惜这样还是n^2的。n还是100w这么凶残。

那么考虑斜率优化。

把w(j,i)带进去。

f[i]=min{f[j]+x[i](sp[i]-sp[j])-spx[i]+spx[j]}+c[i];

可以发现决策有单调性，x=sp[i]-sp[j],y=f[j]-spx[i]+spx[j],k=x[i]。那么就行了。O(n)

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef double D;
const int maxn=1000005;
const double inf=1e30;
ll x[maxn],p[maxn],c[maxn],sp[maxn],spx[maxn],q[maxn],f[maxn];
inline D slope(int i,int j){
    ll dx=sp[i]-sp[j],dy=f[i]-f[j]+spx[i]-spx[j];
    if(!dx) return (dy>=0)?inf:-inf;
    return (D)dy/(D)dx;
}inline void read(ll &x){
    ll r=0,f=1;char ch;
    for(ch=getchar();(ch!='-')&&(ch<'0'||ch>'9');ch=getchar());
    if(ch=='-') f=-1; else r=ch-'0';
    for(ch=getchar();ch>='0'&&ch<='9';ch=getchar())r=r*10+ch-48;
    x=r*f;
}int main(){
    ll n;read(n);
    for(ll i=1;i<=n;i++){
        read(x[i]);read(p[i]);read(c[i]);
        sp[i]=sp[i-1]+p[i];
        spx[i]=spx[i-1]+p[i]*x[i];
    }ll s=0,e=0;q[0]=0;
    for(ll i=1;i<=n;i++){
        while(s<e&&slope(q[s],q[s+1])<=(D)x[i])s++;
        f[i]=f[q[s]]+x[i]*(sp[i]-sp[q[s]])-(spx[i]-spx[q[s]])+c[i];
        while(s<e&&slope(q[e],q[e-1])>=slope(i,q[e]))e--;
        q[++e]=i;
    }printf("%lld\n",f[n]);
    return 0;
}