题解 P2605 【[ZJOI2010]基站选址】

· · 题解

真毒瘤

这个题目耗了我半天。。结果是线段树打错了。。。

略微修改了一下，希望能过审qwq

回归正题：

本蒟蒻用的跟楼上dalao们一样: 线段树+dp

首先当然是先考虑朴素dp啦，相信你既然都来做这题了，朴素的方程自然不用我多说，设f[i][j]表示在前i个村庄内，第j个基站建在i处的最小费用（不考虑i~n的赔偿费用等）

方程为：

f[i][j]=min(f[k][j-1]+pay[k][i])

其中pay[k][i]表示从第k个村庄到第i个村庄的赔偿费用之和

那么我们观察上面这个方程，这个方程是O(n^2k)的,可以发现类似于背包问题，是可以滚掉一维，因为发现f数组第二维只跟上次的值也就是j-1次的值有关，那么我们只要直接利用上一次求出来的值继续dp就行了，不需要多开一维，所以dp方程自然就化为f[i]=min(f[k]+pay[k][i])

那么我们继续思考：主要的时间消耗在了哪里？自然是怎么快速计算pay[k][i]了

那么我们思考：

对于每一个村庄，都有一个范围内需要建立基站，否则就要赔偿，那么我们设第i个村庄的范围为[L,R],如果正在考虑R处建不建基站，那么有下列情况：

$2$、在$R$处建立基站，那么也就相当于最后一个基站设立在$[1,R-1]$这个区间中，找一个费用最小值来转移嘛，还是线段树$qwq

所以我们要开一个线段树来维护f+pay的最小值，要有区间加法和区间查询的操作

那么为了上面的操作，我们还要开几个数组辅助（如果你是dalao当我没说）

st[i]$表示第$i$个村庄对应区间的左端点$L ed[i]$表示第$i$个村庄对应区间的右端点$R

那么当ed_x=i的时候，如果i处不建，那么就要区间加上pay[x]的值，然而可能有很多点的ed都是i，所以我们用链式前向星来保存，具体可以看代码实现

接下来就是美滋滋的代码时间~~~

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 20007
#define int long long
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
struct Edge
{
    int to,nxt;
}edge[N<<2];
struct Tree
{
    int date,mark;
}tr[N<<2];
int n,k,cnt;
int dis[N],val[N],range[N],pay[N],st[N],ed[N],head[N],f[N];
void Add(int u,int v)
{
    edge[++cnt]=(Edge){v,head[u]};
    head[u]=cnt;
}
void Get()
{
    for(int i=1;i<=n;++i)
    {
        st[i]=lower_bound(dis+1,dis+1+n,dis[i]-range[i])-dis;
        ed[i]=lower_bound(dis+1,dis+1+n,dis[i]+range[i])-dis;
        if(dis[ed[i]]>dis[i]+range[i])
            --ed[i];
        Add(ed[i],i);
    }
}
void Pushup(int rt)
{
    tr[rt].date=min(tr[rt<<1].date,tr[rt<<1|1].date);
}
void Build(int rt,int l,int r)
{
    tr[rt].mark=0;
    if(l==r)
    {
        tr[rt].date=f[l];
        return;
    }
    int mid=l+((r-l)>>1);
    Build(rt<<1,l,mid);
    Build(rt<<1|1,mid+1,r);
    Pushup(rt);
}
void Pushdown(int rt)
{
    if(tr[rt].mark)
    {
        tr[rt<<1].date+=tr[rt].mark;
        tr[rt<<1|1].date+=tr[rt].mark;
        tr[rt<<1].mark+=tr[rt].mark;
        tr[rt<<1|1].mark+=tr[rt].mark;
        tr[rt].mark=0;
    }
}
int Search(int rt,int l,int r,int L,int R)
{
//  cout<<"l:"<<l<<" r:"<<r<<" L:"<<L<<" R:"<<R<<endl;
    if(L>R)
        return inf;
    if(L<=l&&r<=R)
        return tr[rt].date;
    int mid=l+((r-l)>>1);
    Pushdown(rt);
    int num=inf;
    if(L<=mid)
        num=min(num,Search(rt<<1,l,mid,L,R));
    if(mid<R)
        num=min(num,Search(rt<<1|1,mid+1,r,L,R));
    return num;
}
void Update(int rt,int l,int r,int L,int R,int c)
{
//  cout<<"l:"<<l<<" r:"<<r<<endl;
    if(L>R)
        return;
    if(L<=l&&r<=R)
    {
        tr[rt].date+=c;
        tr[rt].mark+=c;
        return;
    }
    Pushdown(rt);
    int mid=l+((r-l)>>1);
    if(L<=mid)
        Update(rt<<1,l,mid,L,R,c);
    if(mid<R)
        Update(rt<<1|1,mid+1,r,L,R,c);
    Pushup(rt);
}
void Dp()
{
    int now=0;
    for(int j=1;j<=n;++j)
    {
        f[j]=now+val[j];
        for(int p=head[j];p;p=edge[p].nxt)
        {
            int v=edge[p].to;
            now+=pay[v];
        }
    }
    int ans=f[n];
//  for(int i=1;i<=n;++i)
//  {
//      printf("%d ",f[i]);
//  }
    for(int i=2;i<=k;++i)
    {
        Build(1,1,n);
        for(int j=1;j<=n;++j)
        {
            f[j]=Search(1,1,n,1,j-1)+val[j];
        //  cout<<f[j]<<" ";
            for(int p=head[j];p;p=edge[p].nxt)
            {
                int v=edge[p].to;
                Update(1,1,n,1,st[v]-1,pay[v]);
            }
        }
        ans=min(ans,f[n]);//cout<<"ans:"<<ans<<endl;
    }
    printf("%lld",ans);
}
void Init()
{
    scanf("%lld%lld",&n,&k);
    for(int i=2;i<=n;++i)
        scanf("%lld",&dis[i]);
    for(int i=1;i<=n;++i)
        scanf("%lld",&val[i]);
    for(int i=1;i<=n;++i)
        scanf("%lld",&range[i]);
    for(int i=1;i<=n;++i)
        scanf("%lld",&pay[i]);
    ++n;++k;
    dis[n]=pay[n]=inf;
}
signed main()
{
    Init();
    Get();
    Dp();
    return 0;
}