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

标签： 线段树 DP

题目链接

题解

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

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

这个是\(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;

}