题解 P4655 [CEOI2017] Building Bridges

· · 题解

题目链接

思维历程

首先应当思考不带优化的 dp，再进行优化。

先列出最朴素的式子。

f_i=\min_{j=1}^{j \le i}\{f_j+(h_i-h_j)^2+sum_{i-1}-sum_j\}

其中 sum_j=\sum_{i=1}^ja_i，再将与 i 有关项提出。

f_i={h_i}^2+sum_{i-1}+\min_{j=1}^{j \le i}\{f_j-2h_ih_j+{h_j}^2-sum_j\}

观察到其中有一项为 -2h_ih_j，与 i 和 j 都有关，且结合数据范围达到 10^6，那么就可以采用李超树进行优化。

简单讲一下李超树的实现，插入直线其实就是对一个区间，首先判断其中点，若新加入直线更优直接交换新旧编号，接下来对两端判断，若新直线（此处表示交换后的 x）更优则继续查找下去。

而查询则是正常类似线段树的写法，但是注意要和当前存的直线的取值比较取更优，因为李超树存的其实是可能的最优直线，还是会有例外的，不会的可以左转这里。

首先设 k=-2h_j，x=h_i，b=f_j+{h_j}^2-sum_j（把和 i 有关的设为未知量，用李超树维护之前所有 k 和 b 的最优取值），维护此时的 y 为最小值，其实就是把 y=kx+b 视为一条直线，求对于确定的 x 在之前的哪条直线上的取值最小，得到的就是答案。

对于第一个点直接处理并加入李超树中，对于之后的点先计算取值再加入李超树。

三个小坑点：

本人拙见，如有差错，请赐教。

代码

#include<bits/stdc++.h>
#define ll long long
#define void inline void
#define ls rt<<1
#define rs rt<<1|1
using namespace std;
const ll N=1e6+10;
ll n,h[N],sum[N],dp[N],k[N],b[N],pre[N<<2];
inline ll read(){
    char ch=getchar();ll res=0,f=1;
    while(ch<'0'||'9'<ch){if(ch=='-')f=-1;ch=getchar();}
    while('0'<=ch&&ch<='9') res=res*10+ch-'0',ch=getchar();
    return res*f;
}
inline ll v(ll num,ll x){//对于x在第num条直线上的取值。
    return k[num]*x+b[num];
}
void modify(ll rt,ll l,ll r,ll x){//这里是插入第x条直线。
    ll mid=(l+r)>>1;
    if(v(x,mid)<v(pre[rt],mid)) swap(x,pre[rt]);
    if(v(x,l)<v(pre[rt],l)) modify(ls,l,mid,x);
    if(v(x,r)<v(pre[rt],r)) modify(rs,mid+1,r,x);
}
inline ll query(ll rt,ll l,ll r,ll x){
    if(l==r) return v(pre[rt],x);
    ll mid=(l+r)>>1;
    if(x<=mid) return min(v(pre[rt],x),query(ls,l,mid,x));//记得取min。
    else return min(v(pre[rt],x),query(rs,mid+1,r,x));
}
int main(){
    n=read(),b[0]=1e18;//一开始默认第0条，所以必须初始化。
    for(ll i=1;i<=n;i++) h[i]=read();
    for(ll i=1;i<=n;i++) sum[i]=read(),sum[i]+=sum[i-1];
    k[1]=-2*h[1],b[1]=h[1]*h[1]-sum[1],modify(1,0,N,1);//第一条直接插入。
    for(ll i=2;i<=n;i++){
        dp[i]=query(1,0,N,h[i])+h[i]*h[i]+sum[i-1];
        k[i]=-2*h[i],b[i]=dp[i]+h[i]*h[i]-sum[i],modify(1,0,N,i);
    }
    printf("%lld",dp[n]);
    return 0;
}