P2120 [ZJOI2007] 仓库建设
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:
[code]#include#define ll long longconst int N=1e6+6;const ll inf=1e17;using namespace std;ll Min(ll x,ll y){return xh(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>n; for(int i=1;i |
