首页 > 代码库 > BZOJ 1835 基站选址（线段树优化DP）

BZOJ 1835 基站选址（线段树优化DP）

2024-07-08 23:57:58   223人阅读

题目链接：http://61.187.179.132/JudgeOnline/problem.php?id=1835

题意：有N个村庄坐落在一条直线上，第 i(i>1)个村庄距离第1个村庄的距离为Di。需要在这些村庄中建立不超过K个通讯基站，在第i个村庄建立基站的费用为Ci。如果在距离第i个村 庄不超过Si的范围内建立了一个通讯基站，那么就成它被覆盖了。如果第i个村庄没有被覆盖，则需要向他们补偿，费用为Wi。现在的问题是，选择基站的位 置，使得总费用最小。

思路：


另外，程序中的n=n+1,m=m+1。因为每次使用f[n]更新答案的，而f[n]的含义是在n位置建立一个通讯站，但是显然有时候最优值并不是一定要在n建立一个。将n+1之后，m+1，则m+1个必然建立在n+1，而这一个在我们计算st和ed数组时看出他们是不对前面的有影响的。因此统计f[n+1]才是正确的。

 

struct Node{    int L,R;    i64 Min,det;         void set(i64 x)    {        det+=x;        Min+=x;    }}; Node a[N<<2]; void pushUp(int t){    if(a[t].L==a[t].R) return;    a[t].Min=min(a[t*2].Min,a[t*2+1].Min);} i64 f[N],ans; void build(int t,int L,int R){    a[t].L=L;    a[t].R=R;    a[t].det=0;    if(L==R)    {        a[t].Min=f[L];        return;    }    int mid=(L+R)>>1;    build(t*2,L,mid);    build(t*2+1,mid+1,R);    pushUp(t);} void pushDown(int t){    if(a[t].L==a[t].R) return;    if(a[t].det)    {        a[t*2].set(a[t].det);        a[t*2+1].set(a[t].det);        a[t].det=0;    }}  void add(int t,int L,int R,i64 x){    if(L>a[t].R||R<a[t].L) return;     if(L<=a[t].L&&a[t].R<=R)    {        a[t].set(x);        return;    }         pushDown(t);    add(t*2,L,R,x);    add(t*2+1,L,R,x);    pushUp(t);} i64 query(int t,int L,int R){    if(L>a[t].R||R<a[t].L) return inf;    if(L<=a[t].L&&a[t].R<=R) return a[t].Min;         pushDown(t);    i64 ans=min(query(t*2,L,R),query(t*2+1,L,R));    pushUp(t);    return ans;}   int n,m,d[N],c[N],s[N],w[N];int st[N],ed[N];vector<int> V[N];    int getL(int x,int pos){    int low=1,high=pos,mid;    while(low<=high)    {        mid=(low+high)>>1;        if(d[mid]>=x) high=mid-1;        else low=mid+1;    }    if(high>=1&&d[high]>=x) return high;    return low;} int getR(int x,int pos){    int low=pos,high=n,mid;    while(low<=high)    {        mid=(low+high)>>1;        if(d[mid]>x) high=mid-1;        else low=mid+1;    }    if(low<=n&&d[low]<=x) return low;    return high;} void init(){    int i;    FOR1(i,n)    {        st[i]=getL(d[i]-s[i],i);        ed[i]=getR(d[i]+s[i],i);        V[ed[i]].pb(i);    }}  void DP(){    build(1,0,n);    int i,j,k;    FOR1(i,n)    {        f[i]=query(1,0,i-1)+c[i];        FOR0(j,SZ(V[i]))        {            k=V[i][j];            add(1,0,st[k]-1,w[k]);        }    }    upMin(ans,f[n]);} int main(){    RD(n,m);    int i;    for(i=2;i<=n;i++) RD(d[i]);    FOR1(i,n) RD(c[i]);    FOR1(i,n) RD(s[i]);    FOR1(i,n) RD(w[i]);    FOR1(i,n) f[i]=inf;     init();     ans=inf; n++; m++;    FOR1(i,m) DP();    PR(ans);}

 

 

 


联系
我们