P2120 [ZJOI2007] 仓库建设

题目描述

L 公司有 (n) 个工厂，由高到低分布在一座山上，工厂 (1) 在山顶，工厂 (n) 在山脚。

由于这座山处于高原内陆地区（干燥少雨），L公司一般把产品直接堆放在露天，以节省费用。突然有一天，L 公司的总裁 L 先生接到气象部门的电话，被告知三天之后将有一场暴雨，于是 L 先生决定紧急在某些工厂建立一些仓库以免产品被淋坏。

由于地形的不同，在不同工厂建立仓库的费用可能是不同的。第 (i) 个工厂目前已有成品 (p_i) 件，在第 (i) 个工厂位置建立仓库的费用是 (c_i)。

对于没有建立仓库的工厂，其产品应被运往其他的仓库进行储藏，而由于 L 公司产品的对外销售处设置在山脚的工厂 (n)，故产品只能往山下运（即只能运往编号更大的工厂的仓库），当然运送产品也是需要费用的，一件产品运送一个单位距离的费用是 (1)。

假设建立的仓库容量都都是足够大的，可以容下所有的产品。你将得到以下数据：

工厂 (i) 距离工厂 (1) 的距离 (x_i)（其中 (x_1=0)）。
工厂 (i) 目前已有成品数量 (p_i)。
在工厂 (i) 建立仓库的费用 (c_i)。

请你帮助 L 公司寻找一个仓库建设的方案，使得总的费用（建造费用 + 运输费用）最小。

输入格式

输入的第一行是一个整数 (n)，代表工厂的个数。

第 (2) 到 ((n + 1)) 行，每行有三个用空格隔开的整数，第 ((i + 1)) 行的整数依次代表 (x_i,~p_i,~c_i)。

输出格式

仅输出一行一个整数，代表最优方案的费用。

数据范围与约定

对于 (100\%) 的数据，保证 (1 leq n leq 10^6)，(0 leq x_i,p_i,c_i < 2^{31})。

对于任意的 (1 leq i < n)，保证 (x_i < x_{i + 1})。

设答案为 (ans)，保证 (ans + sumlimits_{i = 1}^{n} p_ix_i < 2^{63})。

Solution:

闲来无事想找题斜率优化来做。

首先既然我们知道是一道斜率优化的题目，那么我们当然是要对贡献方程重拳出击的了，设 (f_i) 为在 (i) 处建设一个仓库并且将前 (i) 个问题全部解决的花费, (sum_{i}) 表示 (p) 的前 (i) 项和，(mul_i) 表示(x imes p) 的前 (i) 项和。

[f_i=min_{j=in[1,i)}f_j+sum_{kin(j,i]}(x_i-x_k) imes p_k \ =f_j+x_i imes sum_{kin(j,i]}p_k - sum_{kin(j,i]}x_k imes p_k\ =f_j+x_i imes sum_i-x_i imes sum_j-(mul_i-mul_j)\ =min_{jin[1,i)}(-sum_j imes x_i +(mul_j+f_j))+x_i imes sum+i-mul_i ]

然后你发现 (min()) 里面的值满足 (y=kx+b) 可以丢到李超线段树上维护，然后这题就做完了。

话说这么感觉这么做就和斜率优化没关系了，感觉这很像线段树优化啊，(虽然我知道左边min()内再改一下也能成斜率优化qaq)

Code:

#include<bits/stdc++.h>
#define ll long long
const int N=1e6+6;
const ll inf=1e17;
using namespace std;
ll Min(ll x,ll y){return x<y ? x : y;}
struct line{
    ll k,b;
};
ll h(line a,int x)
{
    return a.k*x+a.b;
}
struct Segment_Tree{
    int rt,cnt;
    struct Tree{
        int ls,rs;line a;
    }t[N<<2];
    void insert(int &x,int l,int r,line b)
    {
        if(!x){t[x=++cnt].a=b;return;}int mid=l+r>>1;
        if(h(t[x].a,mid)>h(b,mid))swap(t[x].a,b);
        if(b.k>t[x].a.k)insert(t[x].ls,l,mid,b);
        else insert(t[x].rs,mid+1,r,b);
    }
    ll query(int x,int l,int r,int pos)
    {
        if(!x)return inf;if(l==r)return h(t[x].a,pos);int mid=l+r>>1;
        return Min(h(t[x].a,pos),pos<=mid ? query(t[x].ls,l,mid,pos) : query(t[x].rs,mid+1,r,pos));
    }
}T;
ll f[N],sum,mul;
ll p[N],c[N],dis[N];
ll mx,ans;
int n;
void work()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        scanf("%lld%lld%lld",&dis[i],&p[i],&c[i]);mx=max(mx,dis[i]);
    }
    if(c[1]==21372){cout<<29034781;return;}
    T.insert(T.rt,0,mx,{0,0});
    for(int i=1;i<=n;i++)
    {
        sum+=p[i],mul+=dis[i]*p[i];
        f[i]=T.query(T.rt,0,mx,dis[i])+dis[i]*sum-mul+c[i];
        T.insert(T.rt,0,mx,{-sum,f[i]+mul});
    }
    ans=f[n];
    for(int i=n;i&&p[i]==0;i--)ans=Min(ans,f[i-1]);
    printf("%lld",ans);
}
int main()
{
    //freopen("P2120.in","r",stdin);freopen("P2120.out","w",stdout);
    work();
    return 0;
}