bzoj1835[ZJOI2010]base基站选址

据说正解是什么线段树优化DP，但是作为脑子有坑选手，我们需要5k的做法：

主席树+决策单调性.....

F[m][i]表示已经放置了m个基站，第m个基站放置在第i个村庄,第i个村庄及之前的村庄的总最少花费(包括建立基站的花费和赔偿的花费),转移的时候,F[m][i]=min(F[m-1][j]+cost(j,i))+ci

Cost(j,i)表示在点j和点i各建立一个基站，j和i之间不建立基站时，j和i之间需要的总赔偿。

考虑如何快速求出cost(j,i).对于每个村庄k我们可以在位置坐标轴上二分查找,预处理出一个区间[Lk,Rk],表示如果在[Lk,Rk]放一个基站就可以覆盖村庄k。那么只有[Lk,Rk]完全被[j,i]包含的时候才会产生花费.也就是说，问题转化成给定数轴上一堆带权区间，查询被某一个区间完全包含的所有区间的总权值。

某一个区间被另一个区间完全包含，当且仅当这个区间的左右端点都被包含。所以查询可以等价于：对于右端点在查询范围内的区间，有多少对应的左端点大于查询范围的左端点。我们对每个位置建一棵权值线段树，存储从第一个位置到这个位置的所有区间的左端点，在对应的左端点的位置插入这个区间的权值。总之这个cost可以用主席树logn求。

然后考虑分层转移。每次由设置了i个基站的dp数组推出一共设置i+1个基站的DP数组。

接下来我们发现，这个东西有决策单调性（别问我怎么证，我打的表...），于是上单调栈。然后！考试的时候我的DP数组两维的大小开反了，成功炸掉80分。交换数组的两维大小之后A了，真是悲伤的故事….

标算到底是啥

#include<cstdio>

#include<cstring>

#include<cctype>

#include<algorithm>

using namespace std;

template<typename T>inline void read(T &x){

    char ch;while(ch=getchar(),!isdigit(ch));

    x=ch-'';

    while(ch=getchar(),isdigit(ch))x=x*+ch-'';

}

const int maxn=,maxk=;

int f[maxk][maxn];

int d[maxn],c[maxn],s[maxn],w[maxn];

int l[maxn],r[maxn],seq[maxn];

int n,k;

struct node{

    int sum;node *lch,*rch;

}t[maxn*];int cnt=;//11mb

node *root[maxn];

void Insert(node *rt1,node* &rt2,const int &k,const int &w,int l,int r){

    ++cnt;rt2=t+cnt;

    if(l==r){

        rt2->sum=rt1->sum+w;

        return;

    }

    int mid=(l+r)>>;

    if(k<=mid){

        rt2->rch=rt1->rch;

        Insert(rt1->lch,rt2->lch,k,w,l,mid);

    }else{

        rt2->lch=rt1->lch;

        Insert(rt1->rch,rt2->rch,k,w,mid+,r);

    }

    rt2->sum=rt2->lch->sum+rt2->rch->sum;

}

void build_all(){

    root[]=t+;root[]->lch=root[]->rch=t+;

    int cur=;

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

        if(r[seq[i]]>cur){

            while(cur!=r[seq[i]]){

                root[cur+]=root[cur];

                ++cur;

            }

        }

        Insert(root[cur],root[cur],l[seq[i]],w[seq[i]],,n);

    }

    for(int i=cur+;i<=n;++i)root[i]=root[i-];

}

int query(node *rt1,node *rt2,int k,int l,int r){//有多少数字比k大

   // printf("q%d %d",l,r);

    if(l>k){

        return rt2->sum-rt1->sum;

    }

    int mid=(l+r)>>;

    if(k<mid)return query(rt1->lch,rt2->lch,k,l,mid)+query(rt1->rch,rt2->rch,k,mid+,r);

    else return query(rt1->rch,rt2->rch,k,mid+,r);

}

int qsum(int l,int r){//l,r各自有一个基站

    return query(root[l],root[r-],l,,n);

}

bool cmp(const int &a,const int &b){

    return r[a]<r[b];

}

bool cmp2(const int &a,const int &b){

    return l[a]<l[b];

}

int s1[maxn],s2[maxn];

int st[maxn];int top=,mk=;//st:单调栈

int L[maxn],R[maxn];//每个决策对应的左右区间

inline bool inside(int i,int x){

    return L[x]<=i&&i<=R[x];

}

int binary(int l,int r,int x,int a,int b){//在f[l]..f[r]找出第一个决策b比决策a优的位置

    while(l<=r){

        int mid=(l+r)>>;

        if(f[x-][a]+qsum(a,mid)<f[x-][b]+qsum(b,mid))l=mid+;

        else r=mid-;

    }

    return r+;

}

void work(int x){//x-1 -> x

    //使用x个基站，那么至少已经建到了x

    top=;mk=;

/*    st[++top]=x-1;mk=1;

    L[top]=x;R[top]=n;*/

    for(int i=x;i<=n;++i){

        while(top!=&&(i-)<L[top]&&((f[x-][st[top]]+qsum(st[top],L[top]))>(f[x-][i-]+qsum(i-,L[top])))){

            top--;

        }

        //binary

        if(top!=){

            int tmp;

            if(i-<L[top])tmp=binary(L[top],R[top],x,st[top],i-);

            else tmp=binary(i,R[top],x,st[top],i-);

            R[top]=tmp-;

        }

        st[++top]=i-;L[top]=R[top-]+;R[top]=n;

        while(!inside(i,mk))mk++;

        f[x][i]=c[i]+f[x-][st[mk]]+qsum(st[mk],i);//printf("%d %d %d %d %d\n",mk,x-1,st[mk],x,i);

    }

}

int main(){

   // freopen("base.in","r",stdin);

  //  freopen("base.out","w",stdout);

    memset(f,0x7f,sizeof(f));

    read(n);read(k);

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

        read(d[i]);

    }

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

        read(c[i]);

    }

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

        read(s[i]);

        l[i]=lower_bound(d+,d+n+,d[i]-s[i])-d;r[i]=upper_bound(d+,d+n+,d[i]+s[i])-d-;

    }

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

    for(int i=;i<=n;++i)seq[i]=i;

    int sum=;

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

        sum+=w[i];

    }

    if(k==){

        printf("%d\n",sum);

    }else{

        sort(seq+,seq+n+,cmp);

        build_all();

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

            s1[r[i]]+=w[i];

        }

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

            s1[i]+=s1[i-];

        }sort(seq+,seq+n+,cmp2);

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

            s2[l[i]]+=w[i];

        }

        for(int i=n;i>=;--i){

            s2[i]+=s2[i+];

        }

        int ans=sum;

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

            f[][i]=s1[i-]+c[i];

            int tmp=f[][i]+s2[i+];

            if(tmp<ans)ans=tmp;

        }

        for(int j=;j<=k&&j<=n;++j){

            work(j);

        }

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

            for(int j=;j<=k&&j<=n;++j){

                if(f[j][i]+s2[i+]<ans)ans=f[j][i]+s2[i+];

            }

        }

        printf("%d\n",ans);

    }//while(1);

   // fclose(stdin);fclose(stdout);

    return ;

}

bzoj1835[ZJOI2010]base基站选址的相关教程结束。