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 + \sum\limits_{i = 1}^{n} p_ix_i < 2^{63}\)。

Solution:

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

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

\[f_i=\min_{j\ \in[\ 1\ ,\ i\ )}f_j+\sum_{k\ \in\ (\ j\ ,\ i\ ]}(x_i-x_k)\times p_k \]

\[=f_j+x_i\times \sum_{k\ \in\ (\ j\ ,\ i\ ]}p_k – \sum_{k\ \in\ (\ j\ ,\ i\ ]}x_k\times p_k \]

\[=f_j+x_i\times sum_i-x_i\times sum_j-(mul_i-mul_j) \]

\[=\min_{j\ \in\ [\ 1\ ,\ i\ )}(-sum_j\times x_i +(mul_j+f_j))+x_i\times 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;
}

来源链接：https://www.cnblogs.com/LG017/p/18729203