【BZOJ1835】【ZJOI2010】基站选址

Description

有N个村庄坐落在一条直线上，第i(i>1)个村庄距离第1个村庄的距离为Di。需要在这些村庄中建立不超过K个通讯基站，在第i个村庄建立基站的费用为Ci。如果在距离第i个村庄不超过Si的范围内建立了一个通讯基站，那么就成它被覆盖了。如果第i个村庄没有被覆盖，则需要向他们补偿，费用为Wi。现在的问题是，选择基站的位置，使得总费用最小。输入数据 (base.in) 输入文件的第一行包含两个整数N,K，含义如上所述。第二行包含N-1个整数，分别表示D2,D3,…,DN ，这N-1个数是递增的。第三行包含N个整数，表示C1,C2,…CN。第四行包含N个整数，表示S1,S2,…,SN。第五行包含N个整数，表示W1,W2,…,WN。

Input

输入文件的第一行包含两个整数N,K，含义如上所述。

第二行包含N-1个整数，分别表示D2,D3,…,DN ，这N-1个数是递增的。

第三行包含N个整数，表示C1,C2,…CN。

第四行包含N个整数，表示S1,S2,…,SN。

第五行包含N个整数，表示W1,W2,…,WN。

Output

输出文件中仅包含一个整数，表示最小的总费用。

Sample Input

3 2

1 2

2 3 2

1 1 0

10 20 30

Sample Output

4

Hint

40%的数据中，$N \leq 500$；

100%的数据中，$K \leq N,K \leq 100 , N \leq 20000 , Di \leq 10^{9} , Ci \leq 10000，Si \leq 10^9，Wi \leq 10000$ 。

Solution

对于 40％的数据，显然，这是一个简单的 dp，定义 $f_{i,j}$ 表示将第 i 个星球选为第 j 个基站且不考虑之后的星球的费用，显然可以很容易的得到 dp 方程：$f_{i,j} = min(f_{k,j-1} + cost(k,i))+c_{i} $ ；

上文中 $ Cost(i,j) = \Sigma_{k} w_{k} ( d_{i} < d_{k} - s_{k} \wedge d_{k} > d_{j} + s_{k} ) $ 表示 i~j 之间没有被覆盖到的星球的花费之和。暴力计算 cost 函数的时间复杂度为 O(n),故总时间复杂度为$O(kn^2)$ .

对于 100%的数据，考虑进行优化，首先发现，第 j 层的状态只与上一层有关，故考虑压内存，j接下来，我们发现，大量的时间花费计算在 cost 函数上，容易发现，对于一个星球 i，它可以被覆盖的范围一定是一个区间，考虑记录这个区间的左右端点，接下来考虑它没被覆盖的贡献，容易发现，当你选择区间右端点(不含)之后作为即将建立的基站时，若是从左端点(不含)之前的星球所转移过来的，就需要花费该星球的未覆盖费，由于这是一个区间问题，而状态的转移$min(f_{j} + cost(j,i))$也同样是区间内的，因此考虑利用线段树维护$min(f_{j} + cost(j,i))$加速 DP，滚动利用线段树，在推导完第 i 个星球之后,将右端点为 i 的星球的$w_{j}$在线段树上累加到该星球左端点(不含)之前的星球即可，这样处理好细节之后就可以通过此题，时间复杂度为$O(kn \log_{2} n)$，空间复杂度为O(n).

Code

#include <stdio.h>

#define R register

#define mid (l+r>>1)

#define MN 20005

#define MM (1<<16)

#define inf 0x3f3f3f3f

inline int read(){

    R int x; R bool f; R char c;

    for (f=0; (c=getchar())<'0'||c>'9'; f=c=='-');

    for (x=c-'0'; (c=getchar())>='0'&&c<='9'; x=(x<<3)+(x<<1)+c-'0');

    return f?-x:x;

}

int d[MN],T[MM],mark[MM],r[MN],c[MN],w[MN],st[MN],ed[MN],n,k,lk[MN],nxt[MN],head[MN],cnt,f[MN],ans=inf;

inline int min(int a,int b) {return a<b?a:b;}

inline void ins(int x,int y){lk[++cnt]=y,nxt[cnt]=head[x],head[x]=cnt;}

inline int find(int x){

    R int l=1,r=n;

    while(l<r)

        if (d[mid]<x) l=mid+1;

        else r=mid;

    return l;

}

inline void build(int k,int l,int r){

    if (l==r){

        T[k]=f[l];

        return;

    }build(k<<1,l,mid);

    build(k<<1|1,mid+1,r);

    T[k]=min(T[k<<1],T[k<<1|1]);mark[k]=0;

}

inline void pushdown(int k){

    if (!mark[k]) return;

    T[k<<1]+=mark[k],T[k<<1|1]+=mark[k];

    mark[k<<1]+=mark[k],mark[k<<1|1]+=mark[k];

    mark[k]=0;

}

inline void update(int l,int r,int a,int b,int k,int ad){

    if (l>=a&&r<=b){

        T[k]+=ad;

        mark[k]+=ad;

        return;

    }pushdown(k);

    if (a<=mid) update(l,mid,a,b,k<<1,ad);

    if (b>mid) update(mid+1,r,a,b,k<<1|1,ad);

    T[k]=min(T[k<<1],T[k<<1|1]);

}

inline int query(int l,int r,int a,int b,int k){

    if (l==a&&r==b) return T[k];pushdown(k);

    if (b<=mid) return query(l,mid,a,b,k<<1);

    if (a>mid) return query(mid+1,r,a,b,k<<1|1);

    return min(query(l,mid,a,mid,k<<1),query(mid+1,r,mid+1,b,k<<1|1));

}

int main(){

    n=read(),k=read();

    for (R int i=2; i<=n; ++i) d[i]=read();

    for (R int i=1; i<=n; ++i) c[i]=read();

    for (R int i=1; i<=n; ++i) r[i]=read();

    for (R int i=1; i<=n; ++i) w[i]=read();

    d[++n]=inf;++k;

    for (R int i=1; i<=n; ++i){

        st[i]=find(d[i]-r[i]),ed[i]=find(d[i]+r[i]);

        if (d[ed[i]]>r[i]+d[i]) --ed[i];

        ins(ed[i],i);

    }

    for (R int i=1,sum=0; i<=n; ++i){

        f[i]=sum+c[i];

        for (R int j=head[i]; j; j=nxt[j])

            sum+=w[lk[j]];

    }

    for (R int i=2; i<=k; ++i){

        build(1,1,n);

        for (R int j=1; j<=n; ++j){

            if (j>=i)

                f[j]=query(1,n,1,j-1,1)+c[j];

            else f[j]=inf;

            for (R int l=head[j]; l; l=nxt[l])

                if (st[lk[l]]>1)

                    update(1,n,1,st[lk[l]]-1,1,w[lk[l]]);

        }

    }

    printf("%d\n",f[n]);

    return 0;

}

巴特西

【BZOJ1835】【ZJOI2010】基站选址

Description

Input

Output

Sample Input

Sample Output

Hint

Solution

Code

最新文章

热门文章