题解 [ZJOI2010]基站选址

题面

解析

首先考虑一个暴力的DP,

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

那么有(f[i][k]=min(f[j][k-1]+cost(j,i))),(jin[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
",ret);
	return 0;
}