题目
题目链接：https://www.luogu.com.cn/problem/P4655
有 (n) 根柱子依次排列，每根柱子都有一个高度。第 (i) 根柱子的高度为 (h_i)。
现在想要建造若干座桥，如果一座桥架在第 (i) 根柱子和第 (j) 根柱子之间，那么需要 ((h_i-h_j)^2) 的代价。
在造桥前，所有用不到的柱子都会被拆除，因为他们会干扰造桥进程。第 (i) 根柱子被拆除的代价为 (w_i)，注意 (w_i) 不一定非负，因为可能政府希望拆除某些柱子。
现在政府想要知道，通过桥梁把第 (1) 根柱子和第 (n) 根柱子连接的最小代价。注意桥梁不能在端点以外的任何地方相交。
思路
设 (f[i]) 表示一定不拆第 (i) 个柱子，前 (i) 个柱子连接的最小代价。
那么显然有方程
[f[i]=min^{i-1}_{j=1}(f[j]+(h_i-h_j)^2+sum^{i-1}_{k=j+1}w_k)
]
后面的 (sum w) 可以用前缀和优化一下，记 (s_i=sum^{i}_{j=1} w_i)，那么
[f[j]+h_j^2-s_j=2h_ih_j-s_{i-1}+f[i]-h_i^2
]
我们要让截距最小化，将第 (j) 个柱子看做二维平面上一个点 ((h_j,f[j]+h_j^2-s_j))，维护下凸壳，然后用一条斜率为 (2h_i) 的直线去扫。
发现点的横坐标不递增，所以用 cdq 分治离线做一下就好。
注意当两个点的横坐标一致时，要按照纵坐标从小到大排序。
时间复杂度 (O(nlog^2 n))，可以做到 (O(nlog n)) 的。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100010;
int n,top,st[N];
ll f[N],s[N];
ll read()
{
ll d=0,g=1; char ch=getchar();
while (!isdigit(ch)) { if (ch=='-') g=-1; ch=getchar(); }
while (isdigit(ch)) d=(d<<3)+(d<<1)+ch-48,ch=getchar();
return d*g;
}
struct node
{
ll h,x,y;
int id;
}a[N];
bool cmp1(node x,node y)
{
return x.id<y.id;
}
bool cmp2(node x,node y)
{
return x.x!=y.x ? x.x<y.x : x.y<y.y;
}
bool cmp3(node x,node y)
{
return x.h>y.h;
}
double slope(int x,int y)
{
if (a[x].x==a[y].x) return 10000000000000000.0;
return 1.0*(a[y].y-a[x].y)/(a[y].x-a[x].x);
}
void cdq(int l,int r)
{
if (l==r)
{
a[l].x=a[l].h;
a[l].y=f[l]+a[l].h*a[l].h-s[l];
return;
}
int mid=(l+r)>>1;
sort(a+l,a+r+1,cmp1);
cdq(l,mid);
sort(a+l,a+mid+1,cmp2);
sort(a+mid+1,a+r+1,cmp3);
top=0;
for (int i=l;i<=mid;i++)
{
while (top>1 && slope(st[top],st[top-1])>slope(st[top-1],i)) top--;
st[++top]=i;
}
for (int i=mid+1;i<=r;i++)
{
while (top>1 && slope(st[top],st[top-1])>2.0*a[i].h) top--;
int j=st[top];
f[a[i].id]=min(f[a[i].id],f[a[j].id]+(a[i].h-a[j].h)*(a[i].h-a[j].h)+s[a[i].id-1]-s[a[j].id]);
}
cdq(mid+1,r);
}
int main()
{
n=read();
for (int i=1;i<=n;i++) a[i].h=read(),a[i].id=i;
for (int i=1;i<=n;i++) s[i]=s[i-1]+read();
memset(f,0x3f3f3f3f,sizeof(f));
f[1]=0;
cdq(1,n);
printf("%lld",f[n]);
return 0;
}