Description

有 \(n\)根柱子依次排列，每根柱子都有一个高度。第 \(i\) 根柱子的高度为 \(h_i\)。

现在想要建造若干座桥，如果一座桥架在第 ii 根柱子和第 jj 根柱子之间，那么需要 \((h_i-h_j)^2\) 的代价。

在造桥前，所有用不到的柱子都会被拆除，因为他们会干扰造桥进程。第 \(i\) 根柱子被拆除的代价为 \(w_i\)，注意 \(w_i\)不一定非负，因为可能政府希望拆除某些柱子。

现在政府想要知道，通过桥梁把第 \(1\) 根柱子和第 \(n\) 根柱子连接的最小代价。注意桥梁不能在端点以外的任何地方相交。

Solution

一道水题写了好久，小难受。。。

发现那个\(w_i\)好烦，干脆最后全部加上个\(\sum _i\)，在成为桥柱的地方减掉相应的\(w_i\)

此题显然是需要\(cdq\)分治的，或者动态凸包

按照惯例，\(dp\)题目是不会展现转移式子的，毕竟都很好写

注意就是求斜率的时候一定要考虑斜率不存在的情况！！！

Code 

#include
    
     #define max(a,b) ((a)>(b)?(a):(b))#define min(a,b) ((a)<(b)?(a):(b))#define reg register#define db long double#define ll long long#define ri reg int i#define int llinline ll read(){    ll x=0,f=1;char ch=getchar();    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}    return x*f;}const int MN=1e5+5;int n,w[MN],X[MN],Y[MN],f[MN],sum;bool cmpl(int i,int j){return X[i]
     
      >1,i,j;        cdq(l,mid);        for(i=l;i<=mid;++i) lrk[i]=i;    std::sort(lrk+l,lrk+mid+1,cmpl);    for(i=mid+1;i<=r;++i) rrk[i]=i;    std::sort(rrk+mid+1,rrk+r+1,cmpr);        for(tl=0,i=l;i<=mid;++i)    {        while(tl>1&&calc(q[tl],q[tl-1])>=calc(lrk[i],q[tl])) --tl;        q[++tl]=lrk[i];    }        for(hd=1,i=mid+1;i<=r;++i)    {        while(hd
      
       <=(db)2.*X[rrk[i]]) ++hd;        f[rrk[i]]=min(f[rrk[i]],cal(rrk[i],q[hd]));    }        cdq(mid+1,r);}signed main(){    n=read();reg int i;        for(i=1;i<=n;++i) X[i]=read(),f[i]=1ll<<60;        for(i=1;i<=n;++i) w[i]=read(),sum+=w[i];            f[1]=-w[1];        cdq(1,n);        printf("%lld\n",sum+f[n]);        return 0;}
      
     
    

---

Blog来自PaperCloud，未经允许，请勿转载，TKS！