bzoj[1835][ZJOI2010]base 基地选址

bzoj[1835][ZJOI2010]base 基地选址

标签： 线段树 DP

---

题目链接

题解

这个暴力DP的话应该很容易看出来。

dp[i][j]表示造了i个通讯站，并且j是第i个的最小费用。

\[dp[i][j]=min\{dp[i-1][k]+cost(k,j)\}+c[j]
\]

这个是\(O(n^2k)\)的，很明显我们要对其进行优化。

首先i这一维可以滚掉。

而其实麻烦之处就是cost(i,j)这里，我们肯定不能对其进行预处理。只能够利用其本身的一些性质来做。

我们发现，每个人不需要补偿时是在一段区间内的。可以直接先二分这段区间预处理出来。

然后把这些区间按照右端点排序，每扫到右端点就把左端点之前的加上这个区间的值（补偿值）。

具体实现，由于右端点的值域是\([1,n]\)，我们可以沿用一下存邻接表的那套理论。

区间加值的话，用线段树维护一下就好。

感觉线段树实现过程讲的不太清，总结一下算法步骤：

1.每次线段树设为上一次dp的结果（因为要用这个更新啊）。

2.dp[j]直接是线段树中询问[1,j-1] + c[j]。

3.维护补偿的值，在把右端点为j的在线段树中更新[1,左端点-1]。

Code

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<set>
#include<map>
using namespace std;
#define ll long long
#define REP(i,a,b) for(int i=(a),_end_=(b);i<=_end_;i++)
#define DREP(i,a,b) for(int i=(a),_end_=(b);i>=_end_;i--)
#define EREP(i,a) for(int i=start[(a)];i;i=e[i].next)
inline int read()
{
	int sum=0,p=1;char ch=getchar();
	while(!(('0'<=ch && ch<='9') || ch=='-'))ch=getchar();
	if(ch=='-')p=-1,ch=getchar();
	while('0'<=ch && ch<='9')sum=sum*10+ch-48,ch=getchar();
	return sum*p;
}

const int maxn=20020;

int n,k,w[maxn],d[maxn],cost[maxn],s[maxn];
int st[maxn],ed[maxn];
vector <int>g[maxn];
const int inf=0x3f3f3f3f;
void init()
{
	n=read();k=read();
	REP(i,2,n)d[i]=read();
	REP(i,1,n)cost[i]=read();
	REP(i,1,n)s[i]=read();
	REP(i,1,n)w[i]=read();
	n++;k++;
	w[n]=d[n]=inf;
	s[n]=cost[n]=0;
	REP(i,1,n)
	{
		st[i]=lower_bound(d+1,d+n+1,d[i]-s[i])-d;
		ed[i]=lower_bound(d+1,d+n+1,d[i]+s[i])-d;
		if(d[ed[i]]>d[i]+s[i])ed[i]--;
		g[ed[i]].push_back(i);
	}
}

struct node {
	int mn,lz;
	void Merge(node a,node b)
		{
			mn=min(a.mn,b.mn);
		}
};
node c[maxn*4];
int dp[maxn];

#define lc (o<<1)
#define rc (o<<1 | 1)
#define left lc,l,mid
#define right rc,mid+1,r

void make_tree(int o,int l,int r)
{
	c[o].lz=0;
	if(l==r)
	{
		c[o].mn=dp[l];
		return;
	}
	int mid=(l+r)>>1;
	make_tree(left);
	make_tree(right);
	c[o].Merge(c[lc],c[rc]);
}

inline void push_down(int o,int l,int r)
{
	if(c[o].lz)
	{
		c[lc].lz+=c[o].lz;c[rc].lz+=c[o].lz;
		c[lc].mn+=c[o].lz;c[rc].mn+=c[o].lz;
		c[o].lz=0;
	}
}

void update(int ql,int qr,int x,int o,int l,int r)
{
	if(ql>qr)return;
	if(ql<=l && r<=qr)
	{
		c[o].mn+=x;
		c[o].lz+=x;
		return;
	}
	push_down(o,l,r);
	int mid=(l+r)>>1;
	if(ql<=mid)update(ql,qr,x,left);
	if(qr>mid)update(ql,qr,x,right);
	c[o].Merge(c[lc],c[rc]);
}

int query(int ql,int qr,int o,int l,int r)
{
	if(ql>qr)return 0;
	if(ql<=l && r<=qr)
	{
		return c[o].mn;
	}
	push_down(o,l,r);
	int mid=(l+r)>>1,ans=inf;
	if(ql<=mid)ans=min(ans,query(ql,qr,left));
	if(qr>mid)ans=min(ans,query(ql,qr,right));
	return ans;
}

int ans=inf;

void doing()
{
	int sum=0;
	REP(j,1,n)
	{
		dp[j]=sum+cost[j];
		REP(l,0,g[j].size()-1)
		{
			int x=g[j][l];
			sum+=w[x];
		}
	}
	ans=min(ans,dp[n]);

	REP(i,2,k)
	{
		make_tree(1,1,n);
		//REP(j,1,i)dp[j]=dp[j-1]+cost[j];
		REP(j,1,n)
		{
			dp[j]=query(1,j-1,1,1,n)+cost[j];
			//update(j,j,dp[j],1,1,n);
			REP(l,0,g[j].size()-1)
			{
				int x=g[j][l];
				update(1,st[x]-1,w[x],1,1,n);
			}
		}
		ans=min(ans,dp[n]);
	}
	printf("%d\n",ans);
}

int main()
{
	freopen("base.in","r",stdin);
	freopen("base.out","w",stdout);
	init();
	doing();
	return 0;
}