bzoj1835 [ZJOI2010] 基站选址

Description

有N个村庄坐落在一条直线上，第i(i>1)个村庄距离第1个村庄的距离为Di。需要在这些村庄中建立不超过K个通讯基站，在第i个村庄建立基站的费用为Ci。如果在距离第i个村庄不超过Si的范围内建立了一个通讯基站，那么就成它被覆盖了。如果第i个村庄没有被覆盖，则需要向他们补偿，费用为Wi。现在的问题是，选择基站的位置，使得总费用最小。输入数据 (base.in) 输入文件的第一行包含两个整数N,K，含义如上所述。第二行包含N-1个整数，分别表示D2,D3,…,DN ，这N-1个数是递增的。第三行包含N个整数，表示C1,C2,…CN。第四行包含N个整数，表示S1,S2,…,SN。第五行包含N个整数，表示W1,W2,…,WN。

Input

输出文件中仅包含一个整数，表示最小的总费用。

Output

3 2 1 2 2 3 2 1 1 0 10 20 30

Sample Input

Sample Output

40%的数据中，N<=500；
100%的数据中，K<=N，K<=100，N<=20,000，Di<=1000000000，Ci<=10000，Si<=1000000000，Wi<=10000。

正解：$dp$+线段树优化。

设$f[p][i]$表示用$p$个基站，且第$p$个基站在$i$的最小费用，则$f[p][i]=min(f[p-1][j]+cost[j+1][i])$。考虑如何求出$cost[j+1][i]$。

对于每一个村庄，求出它能覆盖的左界和右界，并把村庄按照右界排序。我们递推到$f[p][i]$的时候，发现右端点小于$i$的村庄都是$i$基站不能覆盖的，那么我们在线段树$[1,l-1]$中加入这些点的$w[i]$。

同时我们把所有的$f[p-1][j]$都加入线段树中，那么求$f[p][i]$就直接在线段树中查询区间最小值就行了。最后我们再把$i$以后不能被覆盖的村庄加入答案中就行了。

  1 //It is made by wfj_2048~
  2 #include <algorithm>
  3 #include <iostream>
  4 #include <complex>
  5 #include <cstring>
  6 #include <cstdlib>
  7 #include <cstdio>
  8 #include <vector>
  9 #include <cmath>
 10 #include <queue>
 11 #include <stack>
 12 #include <map>
 13 #include <set>
 14 #define inf (1LL<<60)
 15 #define N (100010)
 16 #define ls (x<<1)
 17 #define rs (x<<1|1)
 18 #define il inline
 19 #define RG register
 20 #define ll long long
 21 #define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
 22 
 23 using namespace std;
 24 
 25 struct data{ ll i,l,r; }a[N],b[N];
 26 
 27 ll f[110][20010],lazy[4*N],sum[4*N],d[N],c[N],s[N],w[N],n,k,ans;
 28 
 29 il ll gi(){
 30     RG ll x=0,q=1; RG char ch=getchar();
 31     while ((ch<'0' || ch>'9') && ch!='-') ch=getchar();
 32     if (ch=='-') q=-1,ch=getchar();
 33     while (ch>='0' && ch<='9') x=x*10+ch-48,ch=getchar();
 34     return q*x;
 35 }
 36 
 37 il ll cmpr(const data &a,const data &b){ return a.r<b.r; }
 38 
 39 il ll findl(RG ll i){
 40     RG ll l=1,r=i,mid,ans;
 41     while (l<=r){
 42     mid=(l+r)>>1;
 43     if (d[i]-d[mid]<=s[i]) ans=mid,r=mid-1;
 44     else l=mid+1;
 45     }
 46     return ans;
 47 }
 48 
 49 il ll findr(RG ll i){
 50     RG ll l=i,r=n,mid,ans;
 51     while (l<=r){
 52     mid=(l+r)>>1;
 53     if (d[mid]-d[i]<=s[i]) ans=mid,l=mid+1;
 54     else r=mid-1;
 55     }
 56     return ans;
 57 }
 58 
 59 il void pushdown(RG ll x){
 60     sum[ls]+=lazy[x],sum[rs]+=lazy[x];
 61     lazy[ls]+=lazy[x],lazy[rs]+=lazy[x],lazy[x]=0; return;
 62 }
 63 
 64 il void build(RG ll x,RG ll l,RG ll r){
 65     lazy[x]=0; if (l==r){ sum[x]=0; return; }
 66     RG ll mid=(l+r)>>1;
 67     build(ls,l,mid),build(rs,mid+1,r);
 68     sum[x]=min(sum[ls],sum[rs]); return;
 69 }
 70 
 71 il void update(RG ll x,RG ll l,RG ll r,RG ll xl,RG ll xr,RG ll v){
 72     if (xl<=l && r<=xr){ sum[x]+=v,lazy[x]+=v; return; }
 73     if (lazy[x]) pushdown(x); RG ll mid=(l+r)>>1;
 74     if (xr<=mid) update(ls,l,mid,xl,xr,v);
 75     else if (xl>mid) update(rs,mid+1,r,xl,xr,v);
 76     else update(ls,l,mid,xl,mid,v),update(rs,mid+1,r,mid+1,xr,v);
 77     sum[x]=min(sum[ls],sum[rs]); return;
 78 }
 79 
 80 il ll query(RG ll x,RG ll l,RG ll r,RG ll xl,RG ll xr){
 81     if (xl<=l && r<=xr) return sum[x];
 82     if (lazy[x]) pushdown(x); RG ll mid=(l+r)>>1;
 83     if (xr<=mid) return query(ls,l,mid,xl,xr);
 84     else if (xl>mid) return query(rs,mid+1,r,xl,xr);
 85     else return min(query(ls,l,mid,xl,mid),query(rs,mid+1,r,mid+1,xr));
 86 }
 87 
 88 il void work(){
 89     n=gi(),k=gi();
 90     for (RG ll i=2;i<=n;++i) d[i]=gi();
 91     for (RG ll i=1;i<=n;++i) c[i]=gi();
 92     for (RG ll i=1;i<=n;++i) s[i]=gi();
 93     for (RG ll i=1;i<=n;++i) w[i]=gi();
 94     for (RG ll i=1;i<=n;++i){
 95     a[i].i=i,a[i].l=findl(i),a[i].r=findr(i);
 96     b[i].i=i,b[i].l=a[i].l,b[i].r=a[i].r;
 97     }
 98     sort(a+1,a+n+1,cmpr);
 99     for (RG ll i=1;i<=n;++i){
100     f[1][i]=c[i]+query(1,1,n,i,i);
101     if (b[i].r<n) update(1,1,n,b[i].r+1,n,w[i]);
102     }
103     for (RG ll p=2,top;p<=k;++p){
104     top=1,build(1,1,n);
105     for (RG ll i=p-1;i<=n;++i) update(1,1,n,i,i,f[p-1][i]);
106     for (RG ll i=p;i<=n;++i){
107         for (;top<=n && a[top].r<i;++top)
108         if (a[top].l>1) update(1,1,n,1,a[top].l-1,w[a[top].i]);
109         f[p][i]=c[i]+query(1,1,n,p-1,i-1);
110     }
111     }
112     ans=inf;
113     for (RG ll p=k;p;--p){
114     build(1,1,n);
115     for (RG ll i=n;i>=p;--i){
116         f[p][i]+=query(1,1,n,i,i),ans=min(ans,f[p][i]);
117         if (b[i].l>1) update(1,1,n,1,b[i].l-1,w[i]);
118     }
119     }
120     printf("%lld
",ans); return;
121 }
122 
123 int main(){
124     File("base");
125     work();
126     return 0;
127 }