题解 [ZJOI2010]基站选址

题解 [ZJOI2010]基站选址

题面

解析

首先考虑一个暴力的DP,

设\(f[i][k]\)表示第\(k\)个基站设在第\(i\)个村庄,且不考虑后面的村庄的最小费用.

那么有\(f[i][k]=\min(f[j][k-1]+cost(j,i))\),\(j\in[1,i-1]\)

其中\(cost(j,i)\)表示从\(j\)到\(i\)中间没有被覆盖的村庄的补偿.

但这显然会T...

首先可以考虑优化掉\(k\),

直接因为只有\(k-1\)有影响,直接提出来放外面循环就行了.

然后要优化掉\(cost(j,i)\)以及找到最小值,

这个可以用线段树来做.

具体来说,首先我们要找到能覆盖村庄\(i\)的最远的两个端点\(st[i]\)(左)和\(ed[i]\)(右)

如果当前到了\(i\)村庄,那么\(ed\)等于\(i\)的村庄\(x\),

在\(i+1\)到\(n\)的计算中,

就要被算到\(1\)到\(st[x]-1\)的村庄的\(cost\)中去了.

因此用邻接表存\(ed\)等于\(i\)的村庄,

再拿一个线段树区间加及求区间最小值就行了.

(线段树中的点\(j\)存的是\(f[j]+\)对以后有贡献的\(cost\))

注意:

• 因为状态没有考虑后面的村庄,所以要在最后面加一个,距离设为inf(同时\(k\)也要++)
• 每次新建一棵线段树,记得清空\(tag\)(WA到吐)

code:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define int long long
#define ls(a) a<<1
#define rs(a) a<<1|1
using namespace std;

inline int read(){
    int sum=0,f=1;char c=getchar();
    while(c>'9'||c<'0'){if(c=='-') f=-1;c=getchar();}
    while(c<='9'&&c>='0'){sum=(sum<<3)+(sum<<1)+c-'0';c=getchar();}
    return sum*f;
}

const int N=20005;
const int M=201;
const int INF=0x3f3f3f3f;
struct tree{int tag,minn,l,r;}t[N<<4];
struct edge{int to,next;}e[N<<1];
int n,K,d[N],c[N],s[N],w[N],f[N];
int st[N],ed[N];
int head[N],cnt;

inline void pushup(int p){
    t[p].minn=min(t[ls(p)].minn,t[rs(p)].minn);
}

inline void pushdown(int p){
    t[ls(p)].minn+=t[p].tag;
    t[rs(p)].minn+=t[p].tag;
    t[ls(p)].tag+=t[p].tag;
    t[rs(p)].tag+=t[p].tag;
    t[p].tag=0;
}

inline void build(int p,int l,int r){
    t[p].l=l;t[p].r=r;t[p].tag=0;
    if(l==r){
        t[p].minn=f[l];
        return ;
    }
    int mid=(l+r)>>1;
    build(ls(p),l,mid);build(rs(p),mid+1,r);
    pushup(p);
}

inline void change(int p,int l,int r,int sum){
    if(l>r) return ;
    if(t[p].l>=l&&t[p].r<=r){
        t[p].minn+=sum;t[p].tag+=sum;
        return ;
    }
    pushdown(p);
    int mid=(t[p].l+t[p].r)>>1;
    if(l<=mid) change(ls(p),l,r,sum);
    if(r>mid) change(rs(p),l,r,sum);
    pushup(p);
}

inline int query(int p,int l,int r){
    if(l>r) return INF;
    if(t[p].l>=l&&t[p].r<=r) return t[p].minn;
    pushdown(p);
    int mid=(t[p].l+t[p].r)>>1,ret=INF;
    if(l<=mid) ret=min(ret,query(ls(p),l,r));
    if(r>mid) ret=min(ret,query(rs(p),l,r));
    pushup(p);
    return ret;
}

inline void add(int x,int y){
    e[++cnt]=(edge){head[x],y};head[x]=cnt;
}

signed main(){
    n=read();K=read();
    for(int i=2;i<=n;i++) d[i]=read();
    for(int i=1;i<=n;i++) c[i]=read();
    for(int i=1;i<=n;i++) s[i]=read();
    for(int i=1;i<=n;i++) w[i]=read();
    d[++n]=INF;
    for(int i=1;i<=n;i++){
        st[i]=lower_bound(d+1,d+n+1,d[i]-s[i])-d;
        ed[i]=upper_bound(d+1,d+n+1,d[i]+s[i])-d-1;
        add(ed[i],i);
    }
    int ret=0;
    for(int i=1;i<=n;i++){
        f[i]=ret+c[i];
        for(int j=head[i];j;j=e[j].to){
            int k=e[j].next;ret+=w[k];
        }
    }
    ret=f[n];
    for(int q=1;q<=K;q++){
        build(1,1,n);
        for(int i=1;i<=n;i++){
            f[i]=query(1,1,i-1)+c[i];
            for(int j=head[i];j;j=e[j].to){
                int k=e[j].next;
                change(1,1,st[k]-1,w[k]);
            }
        }
        ret=min(ret,f[n]);
    }
    printf("%lld\n",ret);
    return 0;
}