[洛谷P2605] ZJOI2016 基站选址

问题描述

有N个村庄坐落在一条直线上，第i(i>1)个村庄距离第1个村庄的距离为Di。需要在这些村庄中建立不超过K个通讯基站，在第i个村庄建立基站的费用为Ci。如果在距离第i个村庄不超过Si的范围内建立了一个通讯基站，那么就村庄被基站覆盖了。如果第i个村庄没有被覆盖，则需要向他们补偿，费用为Wi。现在的问题是，选择基站的位置，使得总费用最小。

输入格式

输入文件的第一行包含两个整数N,K，含义如上所述。

第二行包含N-1个整数，分别表示D2,D3,…,DN ，这N-1个数是递增的。

第三行包含N个整数，表示C1,C2,…CN。

第四行包含N个整数，表示S1,S2,…,SN。

第五行包含N个整数，表示W1,W2,…,WN。

输出格式

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

样例输入

3 2

1 2

2 3 2

1 1 0

10 20 30

样例输出

说明

40%的数据中，N<=500；

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

解析

可以想到是动态规划的题目。设\(f[i][j]\)表示把第j个基站修在第i个村庄且不考虑第i+1到第n个村庄的最小费用。那么，状态转移方程为

\[f[i][j]=min(f[k][j-1]+cost(k,i))
\]

其中\(cost(k,i)\)表示\(k\)到\(i\)的村庄中没有被\(i\)和\(k\)基站覆盖到的村庄所需的赔偿费用。这样做是可能会达到\(O(n^2k)\)的复杂度。考虑如何优化。

对每一个村庄\(i\)求出最左边能够覆盖到它的村庄和最右边能够覆盖到它的村庄(记为\(l[i]\)和\(r[i]\))。那么在\(l[i]\)之前的村庄都无法覆盖到\(i\)。在往\(i+1\)转移的时候，对于村庄\(k\)满足\(r[k]=i\)，如果是从\([1,l[k]-1]\)转移过来的话，一定会赔偿\(k\)，即\([1,l[k]-1]\)的费用都会增加\(k\)的赔偿。所以，用线段树维护\(f[k][j-1]+cost(k,i)\)的值，同时用邻接表记录\(r[k]=i\)的\(k\)，每次转移都区间修改，然后在\([1,i-1]\)中取最小值。

还有一点，由于DP时没有考虑后面的村庄，为了避免漏掉最后一个村庄的情况，我们可以加入第\(n+1\)个村庄，并强制这个村庄上建立第\(k+1\)个基站。

代码

#include <iostream>

#include <cstdio>

#include <algorithm>

#define N 20002

using namespace std;

const int inf=1<<30;

struct SegmentTree{

	int dat,add;

}t[N*4];

int head[N],ver[N*2],nxt[N*2],tot;

int n,k,i,j,x,d[N],c[N],s[N],w[N],l[N],r[N],f[N];

int read()

{

	char c=getchar();

	int w=0;

	while(c<'0'||c>'9') c=getchar();

	while(c<='9'&&c>='0'){

		w=w*10+c-'0';

		c=getchar();

	}

	return w;

}

void insert(int x,int y)

{

	tot++;

	ver[tot]=y;

	nxt[tot]=head[x];

	head[x]=tot;

}

void build(int p,int l,int r)

{

	t[p].add=t[p].dat=0;

	if(l==r){

		t[p].dat=f[l];

		return;

	}

	int mid=(l+r)/2;

	build(p*2,l,mid);

	build(p*2+1,mid+1,r);

	t[p].dat=min(t[p*2].dat,t[p*2+1].dat);

}

void spread(int p)

{

	if(t[p].add){

		t[p*2].dat+=t[p].add;

		t[p*2+1].dat+=t[p].add;

		t[p*2].add+=t[p].add;

		t[p*2+1].add+=t[p].add;

		t[p].add=0;

	}

}

void change(int p,int l,int r,int ql,int qr,int x)

{

	if(ql>qr) return;

	if(ql<=l&&r<=qr){

		t[p].dat+=x;

		t[p].add+=x;

		return;

	}

	int mid=(l+r)/2;

	spread(p);

	if(ql<=mid) change(p*2,l,mid,ql,qr,x);

	if(qr>mid) change(p*2+1,mid+1,r,ql,qr,x);

	t[p].dat=min(t[p*2].dat,t[p*2+1].dat);

}

int ask(int p,int l,int r,int ql,int qr)

{

	if(ql>qr) return 0;

	if(ql<=l&&r<=qr) return t[p].dat;

	int mid=(l+r)/2,ans=1<<30;

	spread(p);

	if(ql<=mid) ans=min(ans,ask(p*2,l,mid,ql,qr));

	if(qr>mid) ans=min(ans,ask(p*2+1,mid+1,r,ql,qr));

	return ans;

}

int main()

{

	n=read(),k=read();

	for(i=2;i<=n;i++) d[i]=read();

	for(i=1;i<=n;i++) c[i]=read();

	for(i=1;i<=n;i++) s[i]=read();

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

	n++;k++;

	d[n]=w[n]=inf;

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

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

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

		if(d[r[i]]>d[i]+s[i]) r[i]--;

		insert(r[i],i);

	}

	int ans=inf;

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

		if(j==1){

			int tmp=0;

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

				f[i]=tmp+c[i];

				for(x=head[i];x;x=nxt[x]) tmp+=w[ver[x]];

			}

		}

		else{

			build(1,1,n);

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

				f[i]=ask(1,1,n,j-1,i-1)+c[i];

				for(x=head[i];x;x=nxt[x]) change(1,1,n,1,l[ver[x]]-1,w[ver[x]]);

			}

		}

		ans=min(ans,f[n]);

	}

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

}

巴特西