视频链接：C121 李超树+DP P4655 [CEOI2017] Building Bridges_哔哩哔哩_bilibili
Luogu P4655 [CEOI2017] Building Bridges
#include <iostream> #include <cstring> #include <algorithm> using namespace std;#define ll long long #define ls u<<1 #define rs u<<1|1 const int N=100005,M=1000005;ll h[N],s[N],k[N],b[N],f[N]; int n,tr[M<<2]; //优势线段的编号 ll Y(int id,int x){ //求Y值return k[id]*x+b[id]; } void change(int u,int l,int r,int id){ //修改int mid=l+r>>1;if(Y(id,mid)<Y(tr[u],mid)) swap(id,tr[u]);if(Y(id,l)<Y(tr[u],l)) change(ls,l,mid,id);if(Y(id,r)<Y(tr[u],r)) change(rs,mid+1,r,id); } ll query(int u,int l,int r,int x){ //查询if(l==r) return Y(tr[u],x);int mid=l+r>>1;ll ans=Y(tr[u],x);if(x<=mid) return min(ans,query(ls,l,mid,x));else return min(ans,query(rs,mid+1,r,x)); } int main(){scanf("%d",&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];k[0]=0,b[0]=1e18; //第0条线段k[1]=-2*h[1];b[1]=h[1]*h[1]-s[1];change(1,1,M,1); //插入第一条线段for(int i=2;i<=n;++i){f[i]=h[i]*h[i]+s[i-1]+query(1,1,M,h[i]);k[i]=-2*h[i];b[i]=f[i]+h[i]*h[i]-s[i];change(1,1,M,i);}printf("%lld",f[n]); }
