题解 [ZJOI2010]基站选址

题面

解析

首先考虑一个暴力的DP,

设\(f[i][k]\)表示第\(k\)个基站设在第\(i\)个村庄,且不考虑后面的村庄的最小费用.

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

其中\(cost(j,i)\)表示从\(j\)到\(i\)中间没有被覆盖的村庄的补偿.

但这显然会T...

首先可以考虑优化掉\(k\),

直接因为只有\(k-1\)有影响,直接提出来放外面循环就行了.

然后要优化掉\(cost(j,i)\)以及找到最小值,

这个可以用线段树来做.

具体来说,首先我们要找到能覆盖村庄\(i\)的最远的两个端点\(st[i]\)(左)和\(ed[i]\)(右)

如果当前到了\(i\)村庄,那么\(ed\)等于\(i\)的村庄\(x\),

在\(i+1\)到\(n\)的计算中,

就要被算到\(1\)到\(st[x]-1\)的村庄的\(cost\)中去了.

因此用邻接表存\(ed\)等于\(i\)的村庄,

再拿一个线段树区间加及求区间最小值就行了.

(线段树中的点\(j\)存的是\(f[j]+\)对以后有贡献的\(cost\))

注意:

因为状态没有考虑后面的村庄,所以要在最后面加一个,距离设为inf(同时\(k\)也要++)
每次新建一棵线段树,记得清空\(tag\)(WA到吐)

code:

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#define int long long

#define ls(a) a<<1

#define rs(a) a<<1|1

using namespace std;

inline int read(){

	int sum=0,f=1;char c=getchar();

	while(c>'9'||c<'0'){if(c=='-') f=-1;c=getchar();}

	while(c<='9'&&c>='0'){sum=(sum<<3)+(sum<<1)+c-'0';c=getchar();}

	return sum*f;

}

const int N=20005;

const int M=201;

const int INF=0x3f3f3f3f;

struct tree{int tag,minn,l,r;}t[N<<4];

struct edge{int to,next;}e[N<<1];

int n,K,d[N],c[N],s[N],w[N],f[N];

int st[N],ed[N];

int head[N],cnt;

inline void pushup(int p){

	t[p].minn=min(t[ls(p)].minn,t[rs(p)].minn);

}

inline void pushdown(int p){

	t[ls(p)].minn+=t[p].tag;

	t[rs(p)].minn+=t[p].tag;

	t[ls(p)].tag+=t[p].tag;

	t[rs(p)].tag+=t[p].tag;

	t[p].tag=0;

}

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

	t[p].l=l;t[p].r=r;t[p].tag=0;

	if(l==r){

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

		return ;

	}

	int mid=(l+r)>>1;

	build(ls(p),l,mid);build(rs(p),mid+1,r);

	pushup(p);

}

inline void change(int p,int l,int r,int sum){

	if(l>r) return ;

	if(t[p].l>=l&&t[p].r<=r){

		t[p].minn+=sum;t[p].tag+=sum;

		return ;

	}

	pushdown(p);

	int mid=(t[p].l+t[p].r)>>1;

	if(l<=mid) change(ls(p),l,r,sum);

	if(r>mid) change(rs(p),l,r,sum);

	pushup(p);

}

inline int query(int p,int l,int r){

	if(l>r) return INF;

	if(t[p].l>=l&&t[p].r<=r) return t[p].minn;

	pushdown(p);

	int mid=(t[p].l+t[p].r)>>1,ret=INF;

	if(l<=mid) ret=min(ret,query(ls(p),l,r));

	if(r>mid) ret=min(ret,query(rs(p),l,r));

	pushup(p);

	return ret;

}

inline void add(int x,int y){

	e[++cnt]=(edge){head[x],y};head[x]=cnt;

}

signed main(){

	n=read();K=read();

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

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

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

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

	d[++n]=INF;

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

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

		ed[i]=upper_bound(d+1,d+n+1,d[i]+s[i])-d-1;

		add(ed[i],i);

	}

	int ret=0;

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

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

		for(int j=head[i];j;j=e[j].to){

			int k=e[j].next;ret+=w[k];

		}

	}

	ret=f[n];

	for(int q=1;q<=K;q++){

		build(1,1,n);

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

			f[i]=query(1,1,i-1)+c[i];

			for(int j=head[i];j;j=e[j].to){

				int k=e[j].next;

				change(1,1,st[k]-1,w[k]);

			}

		}

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

	}

	printf("%lld\n",ret);

	return 0;

}

巴特西

题解 [ZJOI2010]基站选址

题解 [ZJOI2010]基站选址

题面

解析

最新文章

热门文章