题目:

戳这里

题解:
动态规划+线段树优化的一道 狗题 好题
以下设c[i]是i村庄建立基站的费用,w[i]是i村庄没被覆盖的补偿费用
定义状态:f(i,j)表示前j个村子建立了i个基站且第i个基站建立于j号村子的费用(包括前j个村的建站费和补偿费)
先写出朴素DP的方程:f(i,j)=min{f(i-1,k)+cost(k,j)}+c(j),其中1<=k<=j-1,cost(k,j)是只在k和j两点修建基站,对于两点中间村庄的补偿费用
其中第i层的状态只和第i-1层相关,可以降维成f(i)=min{f(j)+cost(j,i)}+c(i),1<=j<=i-1
计算过程:
第一层for循环枚举1~k,第二层for计算f(i)
其中的f(j)+cost(j,i)可以用线段树来求最小值
可是我们发现,计算cost(j,i)是一个O(n^3)的过程,效率过低
那么现在的问题就是如何维护cost
优化:
我们假设f(j)目前已经计算完了,现在想要计算f(j+1)
我们转移每一层(1~K)时,建立一棵线段树,对于每个点k维护f(k)+cost(k,j)(注意这个东西是随着j的增长而变化的)
观察一下方程,可以发现,原方程中每个f(k),1<=k<=j-1是不随着j的增长而变化的,变化的只有cost(k,i)
是什么引起了cost(k,i)的变化呢?从cost(k,i)变化到cost(k,i+1),说明有些本来能被i位置建立的一座基站覆盖到的村子,因为i->i+1而覆盖不到了,需要给他们补偿
那么我们可以预处理出每个村庄的st和ed,分别代表在村庄i左(右)侧建立基站仍能覆盖到村庄i的最远村庄位置,这个可以二分求出,O(nlogn)
每次转移完f(i)时,将ed(x)=i的所有x,将[1,st[x]-1]这段区间在线段树中加上w[x]即可
计算复杂度:
转移K层O(K),对于每层,重新建立线段树O(nlogn),每个点引起一次区间修改O(nlogn),计算最小值n次(nlogn),总时间复杂度O(NKlogN)
细节处理:
实际实现的时候我们发现每层的答案并不一定是f(n),因为最后一个基站不一定建立在最后一个村庄
那么我们开始的时候++n和++K,在最后添加一个距离正无穷,建站费用为0,补偿费用为正无穷的村子
这样之后f(n)就一定是答案了
贴代码:

bzoj1835.cpp
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
#define sc stree[cur]
#define lc stree[cur<<1]
#define rc stree[cur<<1|1]
const int inf=0x3f3f3f3f;
inline int min(int a,int b){return a<b?a:b;}
std::vector<int> endpos[20005];//存储对于每个村庄,有那些村子的ed等于它
int N,K,D[20005],C[20005],S[20005],W[20005],st[20005],ed[20005],f[20005];
void initSE()//二分求出st和ed数组
{
    for(int i=1;i<=N;++i)
    {
        int far=D[i]+S[i];
        int near=D[i]-S[i];
        far=std::lower_bound(D+1,D+1+N,far)-D;
        if(D[far]>D[i]+S[i])--far;
        near=std::lower_bound(D+1,D+1+N,near)-D;
        st[i]=near;
        ed[i]=far;
        endpos[ed[i]].push_back(i);
    }
}
struct Node
{
    int l,r,val,laz;
};
struct Segment_Tree//请无视这翔一样的渣线段树
{
    Node stree[60005];
    void build(int l,int r,int cur=1)
    {
        sc.l=l,sc.r=r;
        if(l==r)
        {
            sc.val=f[l];
            sc.laz=0;
            return;
        }
        int m=(l+r)>>1;
        build(l,m,cur<<1);
        build(m+1,r,cur<<1|1);
        sc.val=min(lc.val,rc.val);
        sc.laz=0;
    }
    void pushdown(int cur)
    {
        if(!sc.laz)return;
        lc.val+=sc.laz;
        rc.val+=sc.laz;
        lc.laz+=sc.laz;
        rc.laz+=sc.laz;
        sc.laz=0;
    }
    int query(int l,int r,int cur=1)
    {
        if(l>r)return 0;
        pushdown(cur);
        if(sc.l==l && sc.r==r)
            return sc.val;
        int m=(sc.l+sc.r)>>1;
        if(r<=m)return query(l,r,cur<<1);
        else if(l>m)return query(l,r,cur<<1|1);
        else return min(query(l,m,cur<<1),query(m+1,r,cur<<1|1));
    }
    void update(int l,int r,int v,int cur=1)
    {
        if(l>r)return;
        pushdown(cur);
        if(sc.l==l && sc.r==r)
        {
            sc.val+=v;
            sc.laz+=v;
            return;
        }
        int m=(sc.l+sc.r)>>1;
        if(r<=m)update(l,r,v,cur<<1);
        else if(l>m)update(l,r,v,cur<<1|1);
        else update(l,m,v,cur<<1),update(m+1,r,v,cur<<1|1);
        sc.val=min(lc.val,rc.val);
    }
}stree;
int DP()
{
    int tmp=0,ans=inf;
    for(int i=1;i<=N;++i)//我特判了只建立一个基站的状况,不知道有没有必要……
 {
        f[i]=tmp+C[i];
        int siz=endpos[i].size();
        for(int j=0;j<siz;++j)
            tmp+=W[endpos[i][j]];
    }
    ans=f[N];
    for(int i=2;i<=K;++i)
    {
        stree.build(1,N);//转移每一层时,都用上一层的答案重新建立线段树
     for(int j=1;j<=N;++j)
        {
            f[j]=stree.query(1,j-1)+C[j];//记录状态
         int siz=endpos[j].size();
            for(int k=0;k<siz;++k)
                stree.update(1,st[endpos[j][k]]-1,W[endpos[j][k]]);//更新可能变化的部分
     }
        ans=min(ans,f[N]);//每一层的时候都需要统计一下答案,因为我们不一定总要建立K个基站,基站建立太多浪费钱的情况也是存在的
 }
    return ans;
}
int main()
{
    scanf("%d%d",&N,&K);
    for(int i=2;i<=N;++i)
        scanf("%d",D+i);
    for(int i=1;i<=N;++i)
        scanf("%d",C+i);
    for(int i=1;i<=N;++i)
        scanf("%d",S+i);
    for(int i=1;i<=N;++i)
        scanf("%d",W+i);
    D[++N]=inf;W[N]=inf;++K;//在结尾增加一个距离无限,没有建站费用,补偿费用为inf的村子
 initSE();
    printf("%d\n",DP());
}

Comments

comments powered by Disqus