bzoj1835[ZJOI2010]基站选址

时间：2021-11-28 12:47:05

主席树+决策单调,重写一遍比之前短多了……题解:http://www.cnblogs.com/liu-runda/p/6051422.html

#include<cstdio>

#include<cstring>

#include<vector>

#include<algorithm>

using namespace std;

const int maxn=;

int n;

struct node{

  int sum;node* ch[];

  node(){}

  node(int x){sum=x;ch[]=ch[]=;}

}t[maxn*],*root[maxn];int cnt=;

node* newnode(int x){t[++cnt]=node(x);return t+cnt;}

void Insert(node* rt0,node* &rt,int l,int r,int k,int x){

  rt=new node(rt0->sum+x);

  if(l==r)return;

  int mid=(l+r)>>;

  if(k<=mid){

    Insert(rt0->ch[],rt->ch[],l,mid,k,x);

    rt->ch[]=rt0->ch[];

  }else{

    Insert(rt0->ch[],rt->ch[],mid+,r,k,x);

    rt->ch[]=rt0->ch[];

  }

}

int query(node* rt0,node* rt1,int l,int r,int ql,int qr){

  if(ql>qr)return ;

  if(ql<=l&&r<=qr)return rt1->sum-rt0->sum;

  int mid=(l+r)>>,ans=;

  if(ql<=mid)ans+=query(rt0->ch[],rt1->ch[],l,mid,ql,qr);

  if(qr>mid) ans+=query(rt0->ch[],rt1->ch[],mid+,r,ql,qr);

  return ans;

}

int f[][maxn];

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

struct data{

  int l,r,w;

}range[maxn];

vector<data> D[maxn];

void solve(int j,int l,int r,int L,int R){

  if(l>r)return;

  int mid=(l+r)>>,g=;

  f[j][mid]=0x7fffffff;

  for(int i=L;i<=R&&i<mid;++i){

    int tmp=f[j-][i]+query(root[i],root[mid-],,n,i+,mid-)+c[mid];

    if(tmp<f[j][mid]){

      f[j][mid]=tmp;g=i;

    }

  }

  solve(j,l,mid-,L,g);solve(j,mid+,r,g,R);

}

int main(){

  int k;scanf("%d%d",&n,&k);

  d[]=0x80808080;d[n+]=0x7fffffff;

  for(int i=;i<=n;++i)scanf("%d",&d[i]);

  for(int i=;i<=n;++i)scanf("%d",&c[i]);

  for(int i=;i<=n;++i)scanf("%d",&s[i]);

  for(int i=;i<=n;++i)scanf("%d",&w[i]);

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

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

    range[i].w=w[i];

    D[range[i].l].push_back(range[i]);

  }

  root[]=t+;root[]->ch[]=root[]->ch[]=t+;root[]->sum=;

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

    root[i]=root[i-];

    for(vector<data>::iterator pt=D[i].begin();pt!=D[i].end();++pt){

      Insert(root[i],root[i],,n,pt->r,pt->w);

    }

  }

  root[n+]=root[n];

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

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

    f[][i]=query(root[],root[i-],,n,,i-)+c[i];//printf("...%d\n",f[1][i]);

    ans=min(ans,f[][i]+query(root[i],root[n],,n,i+,n));//printf("%d\n",ans);

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

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

        solve(j,,n,,n);

    for(int i=;i<=n;++i)ans=min(ans,f[j][i]+query(root[i],root[n],,n,i+,n));

  }

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

  return ;

}

相关文章