【BZOJ1835】基站选址（ZJOI2010）-DP+线段树优化

做法：本题需要用到DP+线段树优化。
首先，很容易想到区间DP的形式。令

}+ci
其中

)。
这个方程的瓶颈在于

cost的计算，直接暴力算肯定会炸，于是我们需要思考一个新的方法。
注意到对于每个村庄，可以覆盖它的建造基站地点是一个区间

)的最小值即可。
于是我们就以

)的时间复杂度完成了这一题。
以下是本人代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf=1000000000ll*1000000000ll;
int n,k,d[20010],s[20010];
int st[20010]={0},ed[20010]={0};
ll c[20010]={0},w[20010],f[20010][2]={0};
ll seg[80010],tag[80010];
int now=0,past=1;
struct interval
{
    int l,r;
    ll w;
}t[20010];

void pushdown(int no)
{
    if (tag[no]!=0)
    {
        seg[no<<1]+=tag[no],seg[no<<1|1]+=tag[no];
        tag[no<<1]+=tag[no],tag[no<<1|1]+=tag[no];
        tag[no]=0;
    }
}

void pushup(int no)
{
    seg[no]=min(seg[no<<1],seg[no<<1|1]);
}

void buildtree(int no,int l,int r)
{
    tag[no]=0;
    if (l==r)
    {
        seg[no]=f[l][past];
        return;
    }
    int mid=(l+r)>>1;
    buildtree(no<<1,l,mid);
    buildtree(no<<1|1,mid+1,r);
    pushup(no);
}

void modify(int no,int l,int r,int s,int t,ll x)
{
    if (l>=s&&r<=t)
    {
        seg[no]+=x;
        tag[no]+=x;
        return;
    }
    int mid=(l+r)>>1;
    pushdown(no);
    if (s<=mid) modify(no<<1,l,mid,s,t,x);
    if (t>mid) modify(no<<1|1,mid+1,r,s,t,x);
    pushup(no);
}

ll query(int no,int l,int r,int s,int t)
{
    if (s>t) return 0;
    if (l>=s&&r<=t) return seg[no];
    int mid=(l+r)>>1;
    ll ans=inf;
    pushdown(no);
    if (s<=mid) ans=min(ans,query(no<<1,l,mid,s,t));
    if (t>mid) ans=min(ans,query(no<<1|1,mid+1,r,s,t));
    return ans;
}

bool cmp(interval a,interval b)
{
    return a.r<b.r;
}

int main()
{
    scanf("%d%d",&n,&k);
    d[1]=0;
    for(int i=2;i<=n;i++)
        scanf("%d",&d[i]);
    for(int i=1;i<=n;i++)
        scanf("%lld",&c[i]);
    for(int i=1;i<=n;i++)
        scanf("%d",&s[i]);
    for(int i=1;i<=n;i++)
        scanf("%lld",&w[i]);

    for(int i=1;i<=n;i++)
    {
        t[i].w=w[i];
        int l,r;
        l=1,r=i;
        while(l<r)
        {
            int mid=(l+r)>>1;
            if (d[mid]>=d[i]-s[i]) r=mid;
            else l=mid+1;
        }
        t[i].l=l;
        l=i,r=n;
        while(l<r)
        {
            int mid=(l+r)>>1;
            if (d[mid+1]<=d[i]+s[i]) l=mid+1;
            else r=mid;
        }
        t[i].r=l;
    }
    sort(t+1,t+n+1,cmp);
    for(int i=1;i<=n;i++)
        if (!st[t[i].r])
        {
            st[t[i].r]=i;
            if (i>1) ed[t[i-1].r]=i-1;
        }
    ed[t[n].r]=n;

    for(int i=1;i<=n;i++)
        f[i][past]=inf;
    ll ans=f[n][past];
    for(int i=1;i<=k+1;i++)
    {
        buildtree(1,0,n);
        for(int j=1;j<=n+1;j++)
        {
            if (st[j-1])
            {
                for(int p=st[j-1];p<=ed[j-1];p++)
                    modify(1,0,n,0,t[p].l-1,t[p].w);
            }
            f[j][now]=query(1,0,n,0,j-1)+c[j];
        }
        ans=min(ans,f[n+1][now]);
        swap(now,past);
    }
    printf("%lld",ans);

    return 0; 
}

【BZOJ1835】基站选址（ZJOI2010）-DP+线段树优化

相关推荐