题目大意
连接两根柱子 \(i,j\) 的代价是 \((h_i-h_j)^2+\sum\limits_{k=j+1}^{i-1}w_k\)，连接具有传递性，求将 \(1,n\) 连接的最小代价。
思路分析
斜率优化 DP 板题。
设 \(f_i\) 表示考虑到前 \(i\) 根柱子并强制选择第 \(i\) 根柱子的最小代价，所求即 \(f_n\)。则容易列出状态转移方程：
\[f_i=\min_{j<i}(f_j+(h_i-h_j)^2+\sum_{k=j+1}^{i-1}w_k)
\]
设 \(s\) 为 \(w\) 的前缀和，即 \(s_i=\sum\limits_{j=1}^iw_j\)，则方程可化为：
\[f_i=\min_{j<i}(f_j+h_i^2-2h_ih_j+h_j^2+s_{i-1}-s_{j})
\]
然后是斜率优化经典操作：
\[\begin{aligned}f_i&=f_j+h_i^2-2h_ih_j+h_j^2+s_{i-1}-s_{j}\\f_i-h_i^2-s_{i-1}&=f_j+h_j^2-s_j-2h_ih_j\\(f_i-h_i^2-s_{i-1})&=(-2h_j)(h_i)+(f_j+h_j^2-s_j)\end{aligned}
\]
设：
\[\begin{cases}y=f_i-h_i^2-s_{i-1}\\k=-2h_j\\x=h_i\\b=f_j+h_j^2-s_j\end{cases}
\]
问题转化为每次插入一条 \(k_i=-2h_i,b_i=f_i+h_i^2-s_i\) 的直线，查询 \(x_i=h_i\) 的最值，用李超线段树优化即可。
代码
自我感觉马蜂可看。
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N=100100,V=1001000;
#define int long long
#define mid ((l+r)>>1)
#define inf 0x3f3f3f3f3f3f3f3f
int n;
int h[N],s[N],f[N];
struct Line{
int k,b;
}line[N];
int calc(int id,int x){
return line[id].k*x+line[id].b;
}
bool Less(int id1,int id2,int x){//比较优劣
return calc(id1,x)<calc(id2,x);
}
struct ST{//简洁的李超线段树
int a[V<<2];
void add(int p,int l,int r,int id){
if(l==r){if(Less(id,a[p],l)) a[p]=id;return ;}
if(Less(id,a[p],mid)) swap(a[p],id);
if(Less(id,a[p],l)) add(p<<1,l,mid,id);
if(Less(id,a[p],r)) add(p<<1|1,mid+1,r,id);
}
int query(int p,int l,int r,int x){
int res=calc(a[p],x);
if(l==r) return res;
if(x<=mid) res=min(res,query(p<<1,l,mid,x));
else res=min(res,query(p<<1|1,mid+1,r,x));
return res;
}
}tree;
signed main(){
scanf("%lld",&n);
for(int i=1;i<=n;i++) scanf("%lld",&h[i]);
for(int i=1;i<=n;i++){
scanf("%lld",&s[i]);
s[i]+=s[i-1];
}
line[0]={0,inf};//初始化第 0 条直线，保证空转移转移不到第 0 条上
line[1]=Line{-2*h[1],h[1]*h[1]-s[1]};//初始化第一条直线
tree.add(1,0,V,1);//加入第一条直线
for(int i=2;i<=n;i++){
f[i]=tree.query(1,0,V,h[i])+h[i]*h[i]+s[i-1];//查询，移项过去得 f[i]
line[i]=Line{-2*h[i],f[i]+h[i]*h[i]-s[i]};//新建直线
tree.add(1,0,V,i);//插入直线
}
cout<<f[n]<<'\n';
return 0;
}