[CEOI2017]Building Bridges
时间限制:1000MS 内存限制:131072KB
难度: \(7.2\)
-
题目描述
有 \(n\) 根柱子依次排列,每根柱子都有一个高度。第 \(i\) 根柱子的高度为 \(h_i\) 。
现在想要建造若干座桥,如果一座桥架在第 \(i\) 根柱子和第 \(j\) 根柱子之间,那么需要 \((h_i-h_j)^2\) 的代价。
在造桥前,所有用不到的柱子都会被拆除,因为他们会干扰造桥进程。第 \(i\) 根柱子被拆除的代价为 \(w_i\),注意 \(w_i\) 不一定非负,因为可能政府希望拆除某些柱子。
现在政府想要知道,通过桥梁把第 \(1\) 根柱子和第 \(n\) 根柱子连接的最小代价。注意桥梁不能在端点以外的任何地方相交。
-
输入格式
第一行一个正整数 \(n\) 。
第二行 \(n\) 个空格隔开的整数,依次表示 \(h_1, h_2, \cdots, h_n\) 。
第三行 \(n\) 个空格隔开的整数,依次表示 \(w_1, w_2, \cdots, w_n\) 。
-
输出格式
输出一行一个整数表示最小代价,注意最小代价不一定是正数。
-
样例输入
1 2 3 |
6 3 8 7 1 6 6 0 -1 9 1 2 0 |
-
样例输出
1 |
17 |
-
数据范围与提示
对于 \(30\%\) 的数据,有 \(1 \leq n \leq 1000\) ;
对于另外 \(40\%\) 的数据,有 \(\left| w_i \right| \leq 20\) ,保证存在一种最优方案,除了头尾两根柱子外,最多只保留两根柱子;
对于 \(100\%\) 的数据,有 \(2 \leq n \leq 10^5\),\(0 \leq h_i,\left| w_i\right| \leq 10^6\) 。
数据来源 LOJ 2483 。
已搬至 YZOJ P4254 。
按照惯例,设 \(f_i\) 为做到第 \(i\) 根柱子时的最小代价。计 \(sumw\) 为 \(w\) 的前缀和。
轻松得到转移方程 \(f_i=\min\limits_{j=1}^{i-1}\{f_j+sumw_{i-1}-sumw_j+(h_i-h_j)^2\}\) ,这样就有了 \(30pts\) 。
不难发现其实这是一个斜率优化的经典模型。对这个转移方程进行一些处理
\(\begin{align} f_i&=f_j+sumw_{i-1}-sumw_j+(h_i-h_j)^2 \\ \underbrace{f_i}_{b_i}&=\underbrace{f_j-sumw_j+h^2_j}_{y_j}-\underbrace{h_i}_{k_i} \cdot \underbrace{2h_j}_{x_j}+\underbrace{sumw_{i-1}+h^2_i}_{const_i} \end{align}\)
但是问题来了,这里的 \(k_i\) 和 \(x_j\) 都不是单调的。哦豁,完蛋,要写 Splay 维护下凸壳了。这个时候就要用到一种神奇的分治算法 —— CDQ分治。
回顾一下斜率优化的写法:把可以实现把一个点加入单调队列的操作是因为加入的 \(x\) 是单调的,可以取队头元素为最小值是因为询问的 \(k\) 是单调的。CDQ 分治就是牢牢抓住这两点进行操作的。
因为是分治,所以要有一个分治区间 \([l, r]\) 表示用 \([l, mid]\) 中所有点的信息去更新 \((mid, r]\) 的最小值。那么如何快速做到这个更新操作呢???很简单,只需要把 \([l, mid]\) 中的点按照 \(x\) 排序,\((mid, r]\) 中的元素按照斜率 \(k\) 排序,这样就可以按照最简单斜率优化的写法去更新了。
直接在里面 std::sort() 复杂度会多个 \(log\)(虽然对于数据水的本题也能过),但是运用归并排序的思想就可以达到 \(O(Nlog^2N)\) 的复杂度。
首先在外面把元素按照斜率 \(k\) 排序,然后开始 CDQ分治。
对于区间 \([l, r]\) ,把其中元素的编号按照与 \(mid\) 的大小进行分类,\(\leq mid\) 的分到左边,\(>mid\) 的分到右边,因为要用 \([l, mid]\) 中的点更新 \((mid, r]\),所以要先把这些点找出来。
接着递归进 \([l, mid]\) ,保证左区间已经被处理过了,才能更新右区间的元素。
现在左区间的点和信息都被处理好了,并且 \(x\) 是单调的(已经被处理好了,详见后述),加上右区间的元素的斜率 \(k\) 是单调的(还没有被处理过),所以就可以把左区间的点加入单调队列,然后去更新右区间的元素。
但是现在 \((mid, r]\) 中的元素只有来自 \([l, mid]\) 的贡献,可能取不到最优解,所以还要递归进 \((mid, r]\) 继续处理右区间。
最后不要忘了,要利用归并排序将 \([l ,r]\) 中 点的 \(x\) 变为单调的,这样才能保证前面操作的正确性。(可以理解为递归进一个区间后,这个区间内点的 \(x\) 就会被处理成单调的,可以进行后续的操作)
这就是 CDQ分治 的大致过程。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 |
#include <cstdio> #include <cstdlib> #include <cstring> #include <climits> #include <algorithm> #define _min(_a,_b) ((_a)<(_b)?(_a):(_b)) typedef long long LLONG; inline int getnum() { register int sgn=1; register char c=getchar(); (c=='-' ? sgn=-1 : 0); while(!(c>='0' && c<='9')) c=getchar(),(c=='-' ? sgn=-1 : 0); register int a=0; while(c>='0' && c<='9') { a*=10;a+=c-'0'; c=getchar(); } return sgn*a; } int idx[105050],tidx[105050]; LLONG h[105050],sw[105050],f[105050]; struct _comp { bool operator ()(const int&a,const int&b)const { return (h[a]<h[b]); } }; struct _point { LLONG x,y; LLONG operator * (const _point&o)const { return (x*o.y-y*o.x); } _point operator - (const _point&o)const { return (_point){x-o.x,y-o.y}; } }glist[105050],list[105050],tlist[105050]; void CDQ_Divide(register int l,register int r) { if(l==r) { glist[l]=(_point){2*h[l],f[l]-sw[l]+(LLONG)h[l]*h[l]}; return; } register int mid=(l+r)>>1,tl=l,tr=mid+1; for(register int i=l;i<=r;i++) if(idx[i]<=mid) tidx[tl++]=idx[i]; else tidx[tr++]=idx[i]; for(register int i=l;i<=r;i++) idx[i]=tidx[i]; CDQ_Divide(l,mid); register int front=0,rear=0; for(register int i=l;i<=mid;i++) { while(front+1<rear && (list[rear-1]-list[rear-2])*(glist[i]-list[rear-1])<=0) rear--; list[rear++]=glist[i]; } for(register int i=mid+1;i<=r;i++) { register int x=idx[i]; struct _point ts=(_point){1,h[x]}; while(front+1<rear && (list[front+1]-list[front])*ts>=0) front++; LLONG tf=list[front].y-(LLONG)h[x]*list[front].x+sw[x-1]+(LLONG)h[x]*h[x]; f[x]=_min(f[x],tf); } CDQ_Divide(mid+1,r); tl=l,tr=mid+1; for(register int i=l;i<=r;i++) if((tl<=mid && glist[tl].x<=glist[tr].x) || tr>r) tlist[i]=glist[tl++]; else tlist[i]=glist[tr++]; for(register int i=l;i<=r;i++) glist[i]=tlist[i]; } int main() { register int N=getnum(); for(register int i=1;i<=N;i++) h[i]=getnum(),idx[i]=i; for(register int i=1;i<=N;i++) sw[i]=sw[i-1]+getnum(); /*for(register int i=2;i<=N;i++) { f[i]=LLONG_MAX; for(register int j=1;j<i;j++) { LLONG ts=f[j]+sw[i-1]-sw[j]+(LLONG)(h[i]-h[j])*(h[i]-h[j]); if(ts<f[i]) f[i]=ts; } }*/ std::sort(&idx[1],&idx[N+1],_comp()); memset(f,0x7F,sizeof(f)),f[1]=0; CDQ_Divide(1,N); printf("%lld\n",f[N]); return 0; } |