题解 P2605 【[ZJOI2010]基站选址】(From luoguBlog)

线段树优化dp

数组f[i][j]表示在前i个村庄内，第j个基站建在i处的最小费用

根据交线牛逼法和王鹤松式可得方程

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

cost(k,i)表示第i~k个村庄之间没有被基站覆盖的村庄所需的赔偿费用，计算费用的复杂度为O(n)

利用二分查找预处理每个位置的需求范围bef[i],beh[i]

之后就是利用线段树维护f[]+cost()的最小值，区间查询区间更新

当beh[x]=i,若i不建造，则加cost(可能存在很多x，前向星或vector存储)

Code:

#include<cstdio>

#include<iostream>

#include<cstring>

#include<algorithm>

#include<queue>

#define ls(k) k<<1

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

using namespace std;

const int N=20010,K=110;

int dis[N],s[N],w[N],c[N],f[N];

int n,m,bef[N],beh[N];

int tot=0,to[N<<1],head[N<<1],nxt[N<<1];

int mn[N<<2],lz[N<<2];

void Add(int x,int y)

{

	to[++tot]=y;

	nxt[tot]=head[x];

	head[x]=tot;

}

void up(int k)

{

	mn[k]=min(mn[ls(k)],mn[rs(k)]);

}

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

{

	lz[k]=0;

	if(l==r)

	{

		mn[k]=f[l];

		return ;

	}

	int mid=l+r>>1;

	build(ls(k),l,mid);

	build(rs(k),mid+1,r);

	up(k);

}

void down(int k)

{

	lz[ls(k)]+=lz[k];

	lz[rs(k)]+=lz[k];

	mn[ls(k)]+=lz[k];

	mn[rs(k)]+=lz[k];

	lz[k]=0;

}

int query(int k,int l,int r,int L,int R)

{

	if(L>R)return 0x3f3f3f3f;

	if(L<=l&&R>=r)return mn[k];

	int mid=l+r>>1;

	if(lz[k])down(k);

	int res=0x3f3f3f3f;

	if(L<=mid)res=min(res,query(ls(k),l,mid,L,R));

	if(mid<R)res=min(res,query(rs(k),mid+1,r,L,R));

	return res;

}

void change(int k,int l,int r,int L,int R,int vl)

{

	if(L>R)return ;

	if(L<=l&&R>=r)

	{

		lz[k]+=vl;

		mn[k]+=vl;

		return ;

	}

	if(lz[k])down(k);

	int mid=l+r>>1;

	if(L<=mid)change(ls(k),l,mid,L,R,vl);

	if(R>mid)change(rs(k),mid+1,r,L,R,vl);

	up(k);

}

int main()

{

	scanf("%d%d",&n,&m);

	for(int i=2;i<=n;i++)scanf("%d",&dis[i]);

	for(int i=1;i<=n;i++)scanf("%d",&c[i]);

	for(int i=1;i<=n;i++)scanf("%d",&s[i]);

	for(int i=1;i<=n;i++)scanf("%d",&w[i]);

	n++,m++;

	dis[n]=w[n]=0x3f3f3f3f;

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

	{

		bef[i]=lower_bound(dis+1,dis+n+1,dis[i]-s[i])-dis;

		beh[i]=lower_bound(dis+1,dis+n+1,dis[i]+s[i])-dis;

		if(dis[beh[i]]>dis[i]+s[i])beh[i]--;

		Add(beh[i],i);

	}

	int now=0;

	for(int j=1;j<=n;j++)

	{

		f[j]=now+c[j];

		for(int i=head[j];i;i=nxt[i])now+=w[to[i]];

	}

	int ans=f[n];

	for(int i=2;i<=m;i++)

	{

		build(1,1,n);

		for(int j=1;j<=n;j++)

		{

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

			for(int p=head[j];p;p=nxt[p])

				change(1,1,n,1,bef[to[p]]-1,w[to[p]]);

		}

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

	}

	cout<<ans<<endl;

	return 0;

}

巴特西

题解 P2605 【[ZJOI2010]基站选址】(From luoguBlog)

最新文章

热门文章