愉快的推式子吧 (ﾉ≧∀≦)ﾉ！
设 $f_i$ 表示前 $i$ 根柱子完工后的最小代价。枚举一个小于 $i$ 的 $j$ ，表示为从 $j$ 向 $i$ 连了一座桥，中间的柱子当然全部推掉，计算一下就好：
$$f_i=\min{f_j+(s_{i-1}-s_j)+(h_i-h_j)^2}$$
*其中 $s$ 为 $w$ 的前缀和。
$$f_i=f_j+(s_{i-1}-s_j)+(h_i-h_j)^2\\f_i=f_j+s_{i-1}-s_j+h_i^2+h_j^2-2h_ih_j\\f_j+s_{i-1}-s_j+h_i^2+h_j^2=2h_ih_j+f_i$$
于是最终式子变成了 $y=kx+b$ 的形式，斜率优化！
但是…… 注意这个式子的 $k$ 不是单调递增的，并且 $x$ 也不是单调递增的！那么我们不能用朴素做法了，也不能用二分…… 难道用 $Splay$ ？(码量巨大) 。
不，用 $CDQ$ 分治。
对于一个 $i$ ，可能可以对 $i$ 做出贡献的只有所有小于 $i$ 的 $j$ 。为了保证 $x$ 单调我们先大力将原来的数组按照 $x$ 从小到大排个序，然后 $CDQ$ 的时候分左右两边，左边的所有元素在初始数组的位置都小于右边的左右元素，也就是说我们直接用左边元素对右边元素做出贡献。
同时这里也保证了左右两边的 $x$ 一定是单调上增的。
我们使用单调队列，扫一遍左边的元素，留下能做贡献的点 (下凸壳上的点)，这时候左边的所有元素可以保证 $x$ 和斜率都是单调上增的。
右边呢？因为直线的斜率是 $2x$ ，而右边的 $x$ 也是单调上增的，所以我们可以愉快的做朴素的单调队列了。
$CDQ$ 分治部分的代码：
void CDQ(int l,int r) {
if(l==r) {/*一个点的时候直接计算 y 值*/
a[l].y=f[a[l].id]-s[a[l].id]+S(a[l].x);
return;
}
int mid=(l+r)>>1;
for(int i=l,c1=l,c2=mid+1;i<=r;++i)
if(a[i].id<=mid) b[c1++]=a[i]; /*编号小的左边去*/
else b[c2++]=a[i]; /*编号大些的右边去*/
for(int i=l;i<=r;++i) a[i]=b[i];
CDQ(l,mid); /*计算出左边所有元素的 f*/
int head=1,tail=0;
static int q[N];
for(int i=l;i<=mid;++i) { /*处理出左边所有元素组成的下凸壳*/
while(head<tail&&slope(q[tail-1],q[tail])>slope(q[tail],i)) --tail;
q[++tail]=i;
}
for(int i=mid+1;i<=r;++i) { /*计算左边元素对右边元素产生的贡献*/
while(head<tail&&slope(q[head],q[head+1])<2*a[i].x) ++head; /*维护队列*/
int x=a[i].id,y=a[q[head]].id;
f[x]=min(f[x],f[y]+s[x-1]-s[y]+S(a[i].x-a[q[head]].x));
/*可能计算多次所以要取 min*/
}
CDQ(mid+1,r);
for(int i=l,c1=l,c2=mid+1;i<=r;++i) /*还原 a 数组至初始状态*/
if(c2>r||(c1<=mid&&a[c1].x<a[c2].x)) b[i]=a[c1++];
else b[i]=a[c2++];
for(int i=l;i<=r;++i) a[i]=b[i];
return;
}
//main 函数中
sort(a+1,a+1+n,cmp),CDQ(1,n); /*排序后 CDQ 开始*/
printf("%lld\n",f[n]); /*输出*/
最后因为存在 $0$ ，在计算斜率的时候需要特判一下。还需要注意一下 $long\ long$ 的问题，记得将 $f$ 数组初始化。
Code:
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N=1e5+2;
const ll inf=1e18+9;
struct point {int x,id;ll y;}a[N],b[N];
ll s[N],w[N],f[N];int n;
template <typename _Tp> inline void IN(_Tp&x) {
char ch;bool flag=0;x=0;
while(ch=getchar(),!isdigit(ch)) if(ch=='-') flag=1;
while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
if(flag) x=-x;
}
ll S(ll x) {return x*x;}
bool cmp(point x,point y) {return x.x<y.x;}
double slope(int i,int j) {
if(a[i].x==a[j].x) {
return a[i].y<a[j].y?inf:-inf;
}return double(a[i].y-a[j].y)/double(a[i].x-a[j].x);
}
void CDQ(int l,int r) {
if(l==r) {a[l].y=f[a[l].id]-s[a[l].id]+S(a[l].x);return;}
int mid=(l+r)>>1;
for(int i=l,c1=l,c2=mid+1;i<=r;++i)
if(a[i].id<=mid) b[c1++]=a[i];
else b[c2++]=a[i];
for(int i=l;i<=r;++i) a[i]=b[i];
CDQ(l,mid);
int head=1,tail=0;
static int q[N];
for(int i=l;i<=mid;++i) {
while(head<tail&&slope(q[tail-1],q[tail])>slope(q[tail],i)) --tail;
q[++tail]=i;
}
for(int i=mid+1;i<=r;++i) {
while(head<tail&&slope(q[head],q[head+1])<2*a[i].x) ++head;
int x=a[i].id,y=a[q[head]].id;
f[x]=min(f[x],f[y]+s[x-1]-s[y]+S(a[i].x-a[q[head]].x));
}
CDQ(mid+1,r);
for(int i=l,c1=l,c2=mid+1;i<=r;++i)
if(c2>r||(c1<=mid&&a[c1].x<a[c2].x)) b[i]=a[c1++];
else b[i]=a[c2++];
for(int i=l;i<=r;++i) a[i]=b[i];
return;
}
int main() {
IN(n);
for(int i=1;i<=n;++i)
IN(a[i].x),a[i].id=i,f[i]=inf;
f[1]=0;
for(int i=1;i<=n;++i) IN(w[i]),s[i]=s[i-1]+w[i];
sort(a+1,a+1+n,cmp),CDQ(1,n);
printf("%lld\n",f[n]);
return 0;
}
0 条评论