题目链接:http://61.187.179.132/JudgeOnline/problem.php?id=1835
题意:有N个村庄坐落在一条直线上,第 i(i>1)个村庄距离第1个村庄的距离为Di。需要在这些村庄中建立不超过K个通讯基站,在第i个村庄建立基站的费用为Ci。如果在距离第i个村 庄不超过Si的范围内建立了一个通讯基站,那么就成它被覆盖了。如果第i个村庄没有被覆盖,则需要向他们补偿,费用为Wi。现在的问题是,选择基站的位 置,使得总费用最小。
思路:
另外,程序中的n=n+1,m=m+1。因
为每次使用f[n]更新答案的,而f[n]的含义是在n位置建立一个通讯站,但是显然有时候最优值并不是一定要在n建立一个。将n+1之后,m+1,则
m+1个必然建立在n+1,而这一个在我们计算st和ed数组时看出他们是不对前面的有影响的。因此统计f[n+1]才是正确的。
struct Node { int L,R; i64 Min,det; void set(i64 x) { det+=x; Min+=x; } }; Node a[N<<2]; void pushUp(int t) { if(a[t].L==a[t].R) return; a[t].Min=min(a[t*2].Min,a[t*2+1].Min); } i64 f[N],ans; void build(int t,int L,int R) { a[t].L=L; a[t].R=R; a[t].det=0; if(L==R) { a[t].Min=f[L]; return; } int mid=(L+R)>>1; build(t*2,L,mid); build(t*2+1,mid+1,R); pushUp(t); } void pushDown(int t) { if(a[t].L==a[t].R) return; if(a[t].det) { a[t*2].set(a[t].det); a[t*2+1].set(a[t].det); a[t].det=0; } } void add(int t,int L,int R,i64 x) { if(L>a[t].R||R<a[t].L) return; if(L<=a[t].L&&a[t].R<=R) { a[t].set(x); return; } pushDown(t); add(t*2,L,R,x); add(t*2+1,L,R,x); pushUp(t); } i64 query(int t,int L,int R) { if(L>a[t].R||R<a[t].L) return inf; if(L<=a[t].L&&a[t].R<=R) return a[t].Min; pushDown(t); i64 ans=min(query(t*2,L,R),query(t*2+1,L,R)); pushUp(t); return ans; } int n,m,d[N],c[N],s[N],w[N]; int st[N],ed[N]; vector<int> V[N]; int getL(int x,int pos) { int low=1,high=pos,mid; while(low<=high) { mid=(low+high)>>1; if(d[mid]>=x) high=mid-1; else low=mid+1; } if(high>=1&&d[high]>=x) return high; return low; } int getR(int x,int pos) { int low=pos,high=n,mid; while(low<=high) { mid=(low+high)>>1; if(d[mid]>x) high=mid-1; else low=mid+1; } if(low<=n&&d[low]<=x) return low; return high; } void init() { int i; FOR1(i,n) { st[i]=getL(d[i]-s[i],i); ed[i]=getR(d[i]+s[i],i); V[ed[i]].pb(i); } } void DP() { build(1,0,n); int i,j,k; FOR1(i,n) { f[i]=query(1,0,i-1)+c[i]; FOR0(j,SZ(V[i])) { k=V[i][j]; add(1,0,st[k]-1,w[k]); } } upMin(ans,f[n]); } int main() { RD(n,m); int i; for(i=2;i<=n;i++) RD(d[i]); FOR1(i,n) RD(c[i]); FOR1(i,n) RD(s[i]); FOR1(i,n) RD(w[i]); FOR1(i,n) f[i]=inf; init(); ans=inf; n++; m++; FOR1(i,m) DP(); PR(ans); }